Sorting linked list

[Gregory Smith]

In article <695 at bentley.UUCP> kwh at bentley.UUCP (KW Heuer) writes:
>Is it possible to implement a quicksort on a linked list directly?  (Just
>wondering; I don't think it would be an improvement on the posted merge
>sort, which is already O(n log n) time and O(1) space.)
>
>Karl W. Z. Heuer (ihnp4!bentley!kwh), The Walking Lint

Good point - it can be done on a doubly-linked list, as long as you have
a 'tail' pointer ( which takes only O(n) if you don't already have one).
The 'qsort' algorithm works its way in from both ends of the list,
swapping things until the list is separated into elements [less than] and
[greater than ] some pivot value. It then recursively qsort's the two
lists independently of each other.
This takes O(n log n) time in the best case and O(log n) space in the
worst case (if you count stack frames).

The rest of this posting is advice for anyone who is thinking of
implementing this ( or any qsort ).

The 'usual' way of picking a pivot is to take the first element in the list.
If the list is sorted already, the two resulting lists are [a single item]
and [the rest of the list]. This is the worst case and it reduces to an
insertion sort, O( n*n ) time. The trick here is to avoid the O(n)
stack usage that would result with a straightforward recursive
implementation. Say qsort(s,f) sorts the list starting at 's' and ending
at 'f'. It ends up with two lists 's1,f1' and 's2,f2'. What it should do
next is to remember the *longest* list in auto space ( done nicely by
setting its own parameters s and f to point to the sublist ) and then call
itself recursively to sort the shortest list. It should then *loop back*
to sort the longest list (if it is more  than one item). Thus a stack frame
is saved while sorting the longer one. Here is a skeleton:

quickie(s,f){
	do{
		...( do partitioning, find s1,f1,s2,f2)...
		...( and sizes n1 and n2 )...

		if( n1 > n2 ){
			s = s1; f = f1;		/* s=s1 normally redudant */
			if( n2>1) quickie(s2,f2);
		}else{
			s = s2; f = f2;		/* f=f2 normally redundant */
			if( n1>1) quickie(s1,f1);
		}
	}while( list_size(s,f) > 1);
}
In the worst case mentioned above, the above code makes no recursive calls.

Also: write this as a separate function which calls itself recursively,
and then call that non-recursively from the actual sort function. That
way things like the 'compare' function address which do not change
during a sort can be stuffed into an extern and will not need to be
passed to each call of quickie ( this can save mucho time and reduces
the stack frame ).  Use as few auto (as opposed to static) variables as
you can get away with in quickie, again to reduce stack space. You
probably only need s and f. Anything which is not needed after the
recursive call can be static.
Finally: if quickie sees a two-item list, it should just compare them,
swap if required, and then return, since the generic qsort algorithm
behaves badly on small lists. This should of course be *after* the
'do{' above.

Why I am I writing all of this? Good question... Mainly because I have
seen quicksort many times in textbooks, but rarely do they discuss the
above points. I guess it is usually 'beyond the scope...'. I even saw
one example which figured out which list was smaller, and then called
itself twice recursively, first sorting the smaller and then the larger.
The reason for this was not given - I assume it was a mistaken attempt
to reduce stack space, based on the way that that is done in the
non-recursive qsort algorithm - but I won't go into that. :-).

Enough Ramblin'...

-- 
"If you aren't making any mistakes, you aren't doing anything".
----------------------------------------------------------------------
Greg Smith     University of Toronto      UUCP: ..utzoo!utcsri!greg