2016/08/17 by Noriyuki Kurosawa, Kurosawa, Noriyuki · 1 voice
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1608.04852
6 pages, program source code in the C language
arxiv created 2016/08/17 · arxiv published 2016/08/17 · arxiv updated 2016/08/18
The linear pivot selection algorithm, known as median-of-medians, makes the worst case complexity of quicksort be O(nln 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.