Hi David,
You wrote to Darin Mcbride:
DN> DN> You aren't right. Quicksort is O(n log n), but can bloat out to 
O(n**2)
DN> DN> under adverse circumstances.
DN>DM>Under mostly pathological circumstances... ;-)
DN>No. Even an already ordered array cripples Hoare's original algorithm.
DN>By now you will have read George White's request (in C_echo) that I add
DN>median-of-three pivot selection to the template I posted here a few weeks
DN>ago. This update goes a long way towards overcoming the uncomfortably high
DN>number of difficult cases that cause Quicksort to get bogged down.
That was supposed to be a _suggestion_, not a request :-)
In my testing (in C so off topic here), quicksort with insertion sort
for short partitions and median of three pivot selection is faster than,
or so similar in speed to that it makes little difference, any of
the other sorts on any data sets I've built except already sorted or
very close to sorted data (when insertion sort is the clear winner).
George
 * SLMR 2.1a * Wastebasket: Something to throw things near.
--- Maximus/2 3.01
---------------