Sorting linked list

[KW Heuer]

In article <669 at bentley.UUCP> mdr at 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.)