Dromey, R. Geoff, Exploiting partial order with quicksort, Department of Computing Science, University of Wollongong, Working Paper 82-14, 1982, 13p.
The widely known Quicksort algorithm does not attempt to actively take advantage of partial order in sorting data. A relatively simple change can be made to the Quicksort strategy to give a bestcase performance of n. for ordered data. with a smooth transition to O(n log n) for the random data case. An attractive attribute of this new algorithm (Transort) Is that its performance for random data matches that for Sedgewlck's claimed best Implementation of Quicksort.