Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!linus!philabs!cmcl2!harvard!seismo!caip!topaz!bentley!kwh
From: kwh@bentley.UUCP (KW Heuer)
Newsgroups: net.lang.c
Subject: Re: Sorting linked list
Message-ID: <671@bentley.UUCP>
Date: Thu, 27-Mar-86 19:56:21 EST
Article-I.D.: bentley.671
Posted: Thu Mar 27 19:56:21 1986
Date-Received: Sun, 20-Apr-86 13:24:41 EST
References: <669@bentley.UUCP>
Organization: AT&T Bell Laboratories, Liberty Corner
Lines: 45

In article <669@bentley.UUCP> mdr@bentley.UUCP (M. Rossner) writes:
>It seems that there is an obvious recursive solution to this
>problem that has not yet been mentioned.

A swap-sort is an obvious way to sort an array, too.

>To sort a linked list (in place, without allocating ANY more memory),

Technically it's not an "in place" sort; recursion consumes stack space.

>Note that this assumes a dummy header with a null key so that the
>head of the list is constant.

Why bother with a dummy node?  Consider this algorithm:

struct foo *insert(list, node) struct foo *list, *node; {
	struct foo **p;
	for (p = &list; *p != NULL && (*p)->key < node->key; p = &(*p)->next);
	node->next = *p;
	*p = node;
	return (list);
}
struct foo *sort(list) struct foo *list; {
	return (list == NULL ? NULL : insert(sort(list->next), list));
}

>Voila! Less than tweny lines of code in its entirety.

I got it in five, and only one local variable.  (No, I don't think I crowded
too much on one line.)

For a once-only application I wouldn't mind using this algorithm.  But for
a general-purpose library routine, I wouldn't want a quadratic algorithm;
I'd use that merge-sort that was recently posted here.

>		-- Hoping never to see you on this newsgroup again --

Stay outa my turf, Marc  :-)

>		-- To the Walking Lint, have a nice weekend! --

Thanks.  (Sorry about posting this to the world.)  See you next week!

Karl W. Z. Heuer (ihnp4!bentley!kwh), The Walking Lint
(Marc and I share an office.  I traded him my C for his K.)