TF>> How do i (quick)sort linked lists?
 DM> Quick sort requires random access which lists don't have.  
 MB> I don't know what your quicksort is, but mine doesn't require random
 MB> access. I would still use an array version instead of a list version
 MB> cause i'm lazy, however, i can write a linked list version that won't
 MB> be *that* slow (i mean, it won't be anymore than O(n log n)).
 MB> Write your quicksort algorithm and i'll see why it can't be applied to
 MB> lists...
Quicksort, by definition, requires random access.  Many methods, such as 
insertion sort, IIRC, can use bidirectional access (being able to move 
forward and backward one at a time) or even unidirectional access (although 
usually at the cost of increased stack space).  Quicksort needs to be able to 
quickly find arbitrary nodes and swap them.
And I think quicksort has O(log n) timing, unless I'm already forgetting the 
standard timings.  :-)  If I'm right, that's a major difference in speed 
between nlgn and lgn.
---
---------------