In a message dated 04-02-98, Darin Mcbride said to David Noon about Sorting
Linked List
Hi Darin,
 DN> There is a minor variant of Quicksort, called 
 DN> Mergesort, for sorting linked lists using Hoare's algorithm.
DM>Doesn't Mergesort require O(n) space?  Quicksort requires 
DM>O(lgn) space... that is a large difference... :-)
Space? You are in the wrong part of the continuum. ... :-)
Both use o(n log n) time. [It's actually a little-o bound.]
The lg(n) space figure is for the size of the stack when unwrapping the
recursion. This enhancement I will address in a later template.
 DN> You aren't right. Quicksort is O(n log n), but can bloat out to O(n**2)
 DN> under adverse circumstances.
DM>Under mostly pathological circumstances... ;-)
No. Even an already ordered array cripples Hoare's original algorithm.
By now you will have read George White's request (in C_echo) that I add
median-of-three pivot selection to the template I posted here a few weeks
ago. This update goes a long way towards overcoming the uncomfortably high
number of difficult cases that cause Quicksort to get bogged down.
So, watch this space for some more code.
Regards
Dave

___
 * MR/2 2.25 #353 * The last thing the world needs is Nerd Technology.
--- Maximus/2 3.01
---------------