Re: Anyone help develop an algorythm?

[dewar@merv.cs.nyu.edu (Robert Dewar)]

<<>There is a variant of quick-sort that works on linked lists.
>The trick is to use the first element in the list as the "pivot" and
>then build up two new linked lists containing the left and right
partitions,
>and then recurse as usual.  I would think this could be generalized
>to handle a linked list of arrays (left as an exercise to the reader ;-).


Could you give me a reference (or two) where I might be able to find the
Quick Sort variation you mentioned?
>>


This is not quick sort at all. The essence of quick sort is the in place
exchange -- otherwise you are just talking about a simple recursive
sort, known for a long time before quicksort was published by Hoare.

The algorithm is trivial enough, just form two lists one of elements
greater than the pivot, one of elements less than the pivot, and then
recursively sort both lists and append one to the other.

However, this algorithm is NEVER preferable to a straight 2-way merge
sort, since its average behavior is the same, and its worst case performance
is quadratic.

The only reasonable way to sort a list is with a two way merge sort. 
Divide the list into equal parts, sort each sublist recurs9ively, and
then do a 2-way merge to form the result. This sort is average and
worst case NlogN, is easy to program, and has no disadvatanges over
other methods that I can see.