Publication Date
1982
Recommended Citation
Dromey, R. Geoff, Exploiting partial order with quicksort, Department of Computing Science, University of Wollongong, Working Paper 82-14, 1982, 13p.
https://ro.uow.edu.au/compsciwp/46
Abstract
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.
COinS