Partial Quicksort and Quickpartitionsort
Conrado Martínez, Uwe Rösler
Abstract
Partial Quicksort sorts the l smallest elements in a list of length n. We provide a complete running time analysis for this combination of Find and Quicksort. Further we give some optimal adapted versions, called Partition Quicksort, with an asymptotic running time c1llnl+c2l+n+o(n). The constant c1 can be as small as the information theoretic lower bound log2 e.
Full Text: PostScript PDF