DN> DM>backward one at a time) or even unidirectional access
 DN> DM>(although usually at the cost of increased stack space).  
 DN> DM>Quicksort needs to be able to quickly find arbitrary nodes 
 DN> DM>and swap them.
 DN> There is a minor variant of Quicksort, called Mergesort, for sorting 
 DN> linked lists using Hoare's algorithm.
sorry, but mergesort has little to do with linked lists, except that
it's possible to write one for linked lists, just like for quicksort,
independently. mergesort uses an approach that's bottom-up, while
quicksort is top-down, and that's the main difference. quicksort splits
an array (or a list) at unpredictable points after some sorting;
mergesort considers the elements and builds them into small
arrays/lists and merge them until they're all merged together. in
mergesort the tree of recursivity is pretty much balanced, while in
quicksort it's a structure dependent on luck.
matju
--- Terminate 4.00/Pro
---------------