Quicksort with median of medians is considered practical

Abstract

The linear pivot selection algorithm, known as median-of-medians, makes the worst case complexity of quicksort be $\mathrm{O}(n\ln n)$. Nevertheless, it has often been said that this algorithm is too expensive to use in quicksort. In this article, we show that we can make the quicksort with this kind of pivot selection approach be efficient.

6 pages, program source code in the C language

Cited by in corpus (2)

• Pattern-defeating Quicksort
• LearnedSort as a learning-augmented SampleSort: Analysis and Parallelization