부산대학교 도서관

In this paper, the authors do an extended and detailed analysis of the dual-pivot Quicksort proposed by Vladimir Yaroslavskiy and used in Oracle's Java runtime library since version 7. Oracle decided to adopt the algorithm based on extensive running time experiments that clearly favored it although, according to many analyses, the dual-pivot variants had not shown any potential for performance gains over classic single-pivot Quicksort. The authors have compared two Java implementations of the Quicksort variants and found that Yaroslavskiy's method actually executes more Java Bytecode instructions on average. In this paper, they extend the analysis to the case where the two pivots are chosen as fixed order statistics of a random sample, and they give the precise leading term of the average number of comparisons, swaps, and executed Java Bytecode instructions. Their results confirm earlier empirical findings that the inherent asymmetries of the partitioning algorithm call for a systematic skew in selecting the pivots, the tuning of which requires a quantitative understanding of the delicate trade-off between partitioning costs and the distribution of subproblem sizes for recursive calls. Moreover, they demonstrate that this tuning is very sensitive to the choice of suitable cost measures, which firmly suggests a detailed analysis instead of focusing only on the number of comparisons and swaps.