MB>> Write your quicksort algorithm and i'll see why it can't be applied to
 MB>> lists...
 DM> Quicksort, by definition, requires random access.  Many methods, such as
 DM> insertion sort, IIRC, can use bidirectional access (being able to move 
"by definition" certainly looks good, but it doesn't explain anything.
1. take the 1st element as the pivot.
2. walk through the list, separate the bigs from the smalls by
building two lists. looks like a zipper that you unzip.
3. process the two lists separately and recursively.
4. unite them with the pivot.
is this a quicksort or not?
 DM> Quicksort needs to be able to quickly find
 DM> arbitrary nodes and swap them.
This ain't no quicksort, afaik.
 DM> And I think quicksort has O(log n) timing, unless I'm already forgetting 
 DM> the standard timings.  :-)  If I'm right, that's a major difference in
 DM> speed between nlgn and lgn.
quicksort, mergesort, heapsort are in n log n time. how do you expect
that sorting a collection of n elements takes less than n time? (unless
it is pre-ordered to a certain extent, in a known manner)
matju
--- Terminate 4.00/Pro
---------------