Sorting linked list

[Gregory Smith]

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.  To sort a linked list
>(in place, without allocating ANY more memory), I just need to sort
			       ^^^^^^^^^^ or does he? see below.
>everything except the first node and then insert the first node into
>this list.

Deleted code says:
Sort_List( List ){
	if( List is 1 element ) return;		/* actually the code said 0 */
	save = dequeue_from_head( List );
	Sort_List( List );		/* sort rest of list */

	... then insert 'save' into 'List' in its correct position ...
}
This has not been mentioned for good reason:
	(1) It takes time proportional to N*N ( we don't like that type
	     thing..) which admittedly is fine for smallish lists

	(2) It takes N ( count 'em, N ) stack frames, which is REALLY
	    NASTY and NOT RECOMMENDED for anything but really small lists.
	    Your working storage ( i.e. your stack frames ) could well
	    take up more room than the list itself. Haven't allocated any
	    memory? Really?

	Moral:    No, Virginia, function calls are *not* free.

>Voila! Less than tweny lines of code in its entirety.  Think recursive, man!

If you want to do an insertion sort, do it iteratively, like they learned
you in school.  It would be even shorter (6 lines?) , use no working storage
other than a pointer or two, and would probably run three times as fast.

If you want to think recursive[ly], do a quick sort :-).
-- 
"If you aren't making any mistakes, you aren't doing anything".
----------------------------------------------------------------------
Greg Smith     University of Toronto      UUCP: ..utzoo!utcsri!greg