The Average Case Analysis of Partition Sorts

Richard Cole, David C. Kandathil

Abstract

This paper introduces a new family of in-place sorting algorithms, the partition sorts. They are appealing both for their relative simplicity and their efficient performance. They perform Θ(n log n) operations on the average, and \(\Theta(n \log^2\!n)\) operations in the worst case.
BibTeX
@inproceedings{cole2004average,
  author = {Richard Cole and David C. Kandathil},
  title = {{The Average Case Analysis of Partition Sorts}},
  booktitle = {ESA},
  year = {2004},
  doi = {10.1007/978-3-540-30140-0\_23},
}

Loading related content...

Figure