DN> There is a minor variant of Quicksort, called 
 DN> Mergesort, for sorting linked lists using Hoare's algorithm.
Doesn't Mergesort require O(n) space?  Quicksort requires O(lgn) space... 
that is a large difference... :-)
 DN> You aren't right. Quicksort is O(n log n), but can bloat out to O(n**2)
 DN> under adverse circumstances.
Under mostly pathological circumstances... ;-)
---
---------------