Optimal Dual-Pivot Quicksort: Exact Comparison Count

摘要

Quicksort, proposed by Hoare in 1961, is a venerable sorting algorithm - it has been thoroughly analyzed, it is taught in basic algorithms classes, and it is routinely used in practice. Can there be anything new about Quicksort today? Dual-pivot quicksort refers to variants of classical quicksort where in the partitioning step two pivots are used to split the input into three segments. Algorithms of this type had been studied by Sedgewick (1975) and by Hennequin (1991), with no further consequences. They received new attention starting from 2009, when a dual-pivot algorithm due to Yaroslavskiy, Bentley, and Bloch replaced the well-engineered quicksort algorithm in Oracle's Java 7 runtime library. An analysis of a variant of this algorithm by Nebel and Wild from 2012, where the two pivots are chosen randomly, showed there are about 1.9n ln n comparisons on average for n input numbers. (Other works ensued. Standard quicksort has 2n ln n expected comparisons. It should be noted that on modem computers parameters other than the comparison count will determine the running time.) In the center of the analysis is the partitioning procedure. Given two pivots, it splits the input keys in 'small' (smaller than small pivot), 'medium' (between the two pivots), 'large' (larger than large pivot). We identify a partitioning strategy with the minimum average number of key comparisons in the case where the pivots are chosen from a random sample. The strategy keeps count of how many large and small elements were seen before and prefers the corresponding pivot. The comparison count is closely related to a 'random walk' on the integers which keeps track of the difference of large and small elements seen so far. An alternative way of understanding what is going on is a Polya urn with three colors. For the fine analysis it is essential to understand the expected number of times this random walk hits zero. The expected number of comparisons can be determined exactly and as a formula up to lower terms: It is 1.8n ln n + 2.38..n+ 1.675 ln n + O(1). Extensions to larger numbers of pivots will be discussed.