In a message dated 03-27-98, Darin Mcbride said to Mathieu Bouchard about
Sorting Linked List
Hi Darin,
DM>Quicksort, by definition, requires random access.  Many 
DM>methods, such as insertion sort, IIRC, can use 
DM>bidirectional access (being able to move forward and 
DM>backward one at a time) or even unidirectional access 
DM>(although usually at the cost of increased stack space).  
DM>Quicksort needs to be able to quickly find arbitrary nodes 
DM>and swap them.
There is a minor variant of Quicksort, called Mergesort, for sorting linked
lists using Hoare's algorithm.
DM>And I think quicksort has O(log n) timing, unless I'm 
DM>already forgetting the standard timings.  :-)  If I'm 
DM>right, that's a major difference in speed between nlgn and 
DM>lgn.
You aren't right. Quicksort is O(n log n), but can bloat out to O(n**2)
under adverse circumstances.
Since I asked participants of this echo to create benchmark programs for
assessing the various algorithms I have posted here, perhaps you might like
to be the first. [I have seen none, as yet.] You can then make an empirical
determination of how fast Quicksort is. I suggest you include in your test
suite some data that are already sorted.
Regards
Dave

___
 * MR/2 2.25 #353 * Windows: Just another pane in the glass.
--- Maximus/2 3.01
---------------