The Experts below are selected from a list of 2793 Experts worldwide ranked by ideXlab platform
Sebastian Wild - One of the best experts on this subject based on the ideXlab platform.
-
QuickXsort: A Fast Sorting Scheme in Theory and Practice
Algorithmica, 2020Co-Authors: Stefan Edelkamp, Armin Weiß, Sebastian WildAbstract:QuickXsort is a highly efficient in-place sequential sorting scheme that mixes Hoare’s Quicksort algorithm with X, where X can be chosen from a wider range of other known sorting algorithms, like Heapsort , Insertionsort and Mergesort . Its major advantage is that QuickXsort can be in-place even if X is not. In this work we provide general transfer theorems expressing the number of comparisons of QuickXsort in terms of the number of comparisons of X. More specifically, if pivots are chosen as medians of (not too fast) growing size samples, the average number of comparisons of QuickXsort and X differ only by o ( n )-terms. For median-of- k pivot selection for some constant k , the difference is a linear term whose coefficient we compute precisely. For instance, median-of-three QuickMergesort uses at most $$n \lg n - 0.8358n + {\mathcal {O}}(\log n)$$ n lg n - 0.8358 n + O ( log n ) comparisons. Furthermore, we examine the possibility of sorting base cases with some other algorithm using even less comparisons. By doing so the average-case number of comparisons can be reduced down to $$n \lg n - 1.4112n + o(n)$$ n lg n - 1.4112 n + o ( n ) for a remaining gap of only 0.0315 n comparisons to the known lower bound (while using only $${\mathcal {O}}(\log n)$$ O ( log n ) additional space and $${\mathcal {O}}(n\log n)$$ O ( n log n ) time overall). Implementations of these sorting strategies show that the algorithms challenge well-established library implementations like Musser’s Introsort .
-
dual pivot and beyond the potential of multiway partitioning in Quicksort
Information Technology, 2018Co-Authors: Sebastian WildAbstract:Abstract Since 2011 the Java runtime library uses a Quicksort variant with two pivot elements. For reasons that remained unclear for years it is faster than the previous Quicksort implementation by more than 10 %; this is not only surprising because the previous code was highly-tuned and is used in many programming libraries, but also since earlier theoretical investigations suggested that using several pivots in Quicksort is not helpful. In my dissertation I proved by a comprehensive mathematical analysis of all sensible Quicksort partitioning variants that (a) indeed there is hardly any advantage to be gained from multiway partitioning in terms of the number of comparisons (and more generally in terms of CPU costs), but (b) multiway partitioning does significantly reduce the amount of data to be moved between CPU and main memory. Moreover, this more efficient use of the memory hierarchy is not achieved by any of the other well-known optimizations of Quicksort, but only through the use of several pivots.
-
analysis of pivot sampling in dual pivot Quicksort a holistic analysis of yaroslavskiy s partitioning scheme
Algorithmica, 2016Co-Authors: Markus E. Nebel, Sebastian Wild, Conrado MartinezAbstract:The new dual-pivot Quicksort by Vladimir Yaroslavskiy--used in Oracle's Java runtime library since version 7--features intriguing asymmetries. They make a basic variant of this algorithm use less comparisons than classic single-pivot Quicksort. In this paper, we extend the analysis to the case where the two pivots are chosen as fixed order statistics of a random sample. Surprisingly, dual-pivot Quicksort then needs more comparisons than a corresponding version of classic Quicksort, so it is clear that counting comparisons is not sufficient to explain the running time advantages observed for Yaroslavskiy's algorithm in practice. Consequently, we take a more holistic approach and give also the precise leading term of the average number of swaps, the number of executed Java Bytecode instructions and the number of scanned elements, a new simple cost measure that approximates I/O costs in the memory hierarchy. We determine optimal order statistics for each of the cost measures. It turns out that the asymmetries in Yaroslavskiy's algorithm render pivots with a systematic skew more efficient than the symmetric choice. Moreover, we finally have a convincing explanation for the success of Yaroslavskiy's algorithm in practice: compared with corresponding versions of classic single-pivot Quicksort, dual-pivot Quicksort needs significantly less I/Os, both with and without pivot sampling.
-
dual pivot Quicksort and beyond analysis of multiway partitioning and its practical potential
2016Co-Authors: Sebastian WildAbstract:Multiway Quicksort, i.e., partitioning the input in one step around several pivots, has received much attention since Java 7’s runtime library uses a new dual-pivot method that outperforms by far the old Quicksort implementation. The success of dual-pivot Quicksort is most likely due to more efficient usage of the memory hierarchy, which gives reason to believe that further improvements are possible with multiway Quicksort. In this dissertation, I conduct a mathematical average-case analysis of multiway Quicksort including the important optimization to choose pivots from a sample of the input. I propose a parametric template algorithm that covers all practically relevant partitioning methods as special cases, and analyze this method in full generality. This allows me to analytically investigate in depth what effect the parameters of the generic Quicksort have on its performance. To model the memory-hierarchy costs, I also analyze the expected number of scanned elements, a measure for the amount of data transferred from memory that is known to also approximate the number of cache misses very well. The analysis unifies previous analyses of particular Quicksort variants under particular cost measures in one generic framework. A main result is that multiway partitioning can reduce the number of scanned elements significantly, while it does not save many key comparisons; this explains why the earlier studies of multiway Quicksort did not find it promising. A highlight of this dissertation is the extension of the analysis to inputs with equal keys. I give the first analysis of Quicksort with pivot sampling and multiway partitioning on an input model with equal keys.
-
average case and distributional analysis of dual pivot Quicksort
ACM Transactions on Algorithms, 2015Co-Authors: Sebastian Wild, Markus E. Nebel, Ralph NeiningerAbstract:In 2009, Oracle replaced the long-serving sorting algorithm in its Java 7 runtime library by a new dual-pivot Quicksort variant due to Vladimir Yaroslavskiy. The decision was based on the strikingly good performance of Yaroslavskiy's implementation in running time experiments. At that time, no precise investigations of the algorithm were available to explain its superior performance—on the contrary: previous theoretical studies of other dual-pivot Quicksort variants even discouraged the use of two pivots. In 2012, two of the authors gave an average case analysis of a simplified version of Yaroslavskiy's algorithm, proving that savings in the number of comparisons are possible. However, Yaroslavskiy's algorithm needs more swaps, which renders the analysis inconclusive.To force the issue, we herein extend our analysis to the fully detailed style of Knuth: we determine the exact number of executed Java Bytecode instructions. Surprisingly, Yaroslavskiy's algorithm needs sightly more Bytecode instructions than a simple implementation of classic Quicksort—contradicting observed running times. As in Oracle's library implementation, we incorporate the use of Insertionsort on small subproblems and show that it indeed speeds up Yaroslavskiy's Quicksort in terms of Bytecodes; but even with optimal Insertionsort thresholds, the new Quicksort variant needs slightly more Bytecode instructions on average.Finally, we show that the (suitably normalized) costs of Yaroslavskiy's algorithm converge to a random variable whose distribution is characterized by a fixed-point equation. From that, we compute variances of costs and show that for large n, costs are concentrated around their mean.
Mounir Hamdi - One of the best experts on this subject based on the ideXlab platform.
-
efficient and scalable Quicksort on a linear array with a reconfigurable pipelined bus system
Future Generation Computer Systems, 1998Co-Authors: Yi Pan, Mounir HamdiAbstract:Abstract Based on the current fiber optic technology, a new computational model, called a linear array with a reconfigurable pipelined abus system (LARPBS), is proposed in this paper. A parallel Quicksort algorithm is implemented on the model, and its time complexity is analyzed. For a set of N numbers, the Quicksort algorithm reported in this paper runs in O ( log 2 N ) average time on a linear array with a reconfigurable pipelined bus system of size N . If the number of processors available is reduced to P , where P N , the algorithm runs in O(( N P ) log 2 N) average time and is still scalable. Besides proposing a new algorithm on the model, some basic data movement operations involved in the algorithm are discussed. We believe that these operations can be used to design other parallel algorithms on the same model. Future research in this area is also identified in this paper.
-
Quicksort on a linear array with a reconfigurable pipelined bus system
International Symposium on Parallel Architectures Algorithms and Networks, 1996Co-Authors: Yi Pan, Mounir HamdiAbstract:Based on the current fiber optic technology, a new computational model, called a linear array with a reconfigurable pipelined bus system (LARPBS), is proposed in this paper. A parallel Quicksort algorithm is implemented on the model, and its time complexity is analyzed. For a set of N numbers, the Quicksort algorithm reported in this paper runs in O(log/sub 2/N) average time on a linear array with a reconfigurable pipelined bus system of size N. Besides proposing a new algorithm on the model, some basic data movement operations involved in the algorithm are discussed. We believe that these operations can be used to design other parallel algorithms on the same model. Future research in this area is also identified in this paper.
Martin Dietzfelbinger - One of the best experts on this subject based on the ideXlab platform.
-
how good is multi pivot Quicksort
ACM Transactions on Algorithms, 2016Co-Authors: Martin Aumuller, Martin Dietzfelbinger, Pascal KlaueAbstract:Multi-Pivot Quicksort refers to variants of classical Quicksort where in the partitioning step k pivots are used to split the input into k + 1 segments. For many years, multi-pivot Quicksort was regarded as impractical, but in 2009 a two-pivot approach by Yaroslavskiy, Bentley, and Bloch was chosen as the standard sorting algorithm in Sun’s Java 7. In 2014 at ALENEX, Kushagra et al. introduced an even faster algorithm that uses three pivots. This article studies what possible advantages multi-pivot Quicksort might offer in general. The contributions are as follows: Natural comparison-optimal algorithms for multi-pivot Quicksort are devised and analyzed. The analysis shows that the benefits of using multiple pivots with respect to the average comparison count are marginal and these strategies are inferior to simpler strategies such as the well-known median-of-k approach. A substantial part of the partitioning cost is caused by rearranging elements. A rigorous analysis of an algorithm for rearranging elements in the partitioning step is carried out, observing mainly how often array cells are accessed during partitioning. The algorithm behaves best if three to five pivots are used. Experiments show that this translates into good cache behavior and is closest to predicting observed running times of multi-pivot Quicksort algorithms. Finally, it is studied how choosing pivots from a sample affects sorting cost. The study is theoretical in the sense that although the findings motivate design recommendations for multipivot Quicksort algorithms that lead to running-time improvements over known algorithms in an experimental setting, these improvements are small.
-
optimal partitioning for dual pivot Quicksort
ACM Transactions on Algorithms, 2015Co-Authors: Martin Aumuller, Martin DietzfelbingerAbstract: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. This can be done in different ways, giving rise to different algorithms. Recently, a dual-pivot algorithm due to Yaroslavskiy received much attention, because it replaced the well-engineered Quicksort algorithm in Oracle’s Java 7 runtime library. Nebel and Wild (ESA 2012) analyzed this algorithm and showed that on average it uses 1.9nln n + O(n) comparisons to sort an input of size n, beating standard Quicksort, which uses 2nln n + O(n) comparisons. We introduce a model that captures all dual-pivot algorithms, give a unified analysis, and identify new dual-pivot algorithms that minimize the average number of key comparisons among all possible algorithms up to a linear term. This minimum is 1.8nln n + O(n). For the case that the pivots are chosen from a small sample, we include a comparison of dual-pivot Quicksort and classical Quicksort. Specifically, we show that dual-pivot Quicksort benefits from a skewed choice of pivots. We experimentally evaluate our algorithms and compare them to Yaroslavskiy’s algorithm and the recently described 3-pivot Quicksort algorithm of Kushagra et al. (ALENEX 2014).
-
how good is multi pivot Quicksort
arXiv: Data Structures and Algorithms, 2015Co-Authors: Martin Aumuller, Martin Dietzfelbinger, Pascal KlaueAbstract:Multi-Pivot Quicksort refers to variants of classical Quicksort where in the partitioning step $k$ pivots are used to split the input into $k + 1$ segments. For many years, multi-pivot Quicksort was regarded as impractical, but in 2009 a 2-pivot approach by Yaroslavskiy, Bentley, and Bloch was chosen as the standard sorting algorithm in Sun's Java 7. In 2014 at ALENEX, Kushagra et al. introduced an even faster algorithm that uses three pivots. This paper studies what possible advantages multi-pivot Quicksort might offer in general. The contributions are as follows: Natural comparison-optimal algorithms for multi-pivot Quicksort are devised and analyzed. The analysis shows that the benefits of using multiple pivots with respect to the average comparison count are marginal and these strategies are inferior to simpler strategies such as the well known median-of-$k$ approach. A substantial part of the partitioning cost is caused by rearranging elements. A rigorous analysis of an algorithm for rearranging elements in the partitioning step is carried out, observing mainly how often array cells are accessed during partitioning. The algorithm behaves best if 3 to 5 pivots are used. Experiments show that this translates into good cache behavior and is closest to predicting observed running times of multi-pivot Quicksort algorithms. Finally, it is studied how choosing pivots from a sample affects sorting cost. The study is theoretical in the sense that although the findings motivate design recommendations for multipivot Quicksort algorithms that lead to running time improvements over known algorithms in an experimental setting, these improvements are small.
-
optimal partitioning for dual pivot Quicksort
International Colloquium on Automata Languages and Programming, 2013Co-Authors: Martin Aumuller, Martin DietzfelbingerAbstract: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. This can be done in different ways, giving rise to different algorithms. Recently, a dual pivot algorithm due to Yaroslavskiy received much attention, because it replaced the well-engineered Quicksort algorithm in Oracle's Java 7 runtime library. Nebel and Wild (ESA 2012) analyzed this algorithm and showed that on average it uses 1.9nln n+O(n) comparisons to sort an input of size n, beating standard Quicksort, which uses 2nln n+O(n) comparisons. We introduce a model that captures all dual pivot algorithms, give a unified analysis, and identify new dual pivot algorithms that minimize the average number of key comparisons among all possible algorithms up to lower order or linear terms. This minimum is 1.8n ln n+O(n).
-
optimal partitioning for dual pivot Quicksort
arXiv: Data Structures and Algorithms, 2013Co-Authors: Martin Aumuller, Martin DietzfelbingerAbstract: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. This can be done in different ways, giving rise to different algorithms. Recently, a dual-pivot algorithm proposed by Yaroslavskiy received much attention, because a variant of it replaced the well-engineered Quicksort algorithm in Sun's Java 7 runtime library. Nebel and Wild (ESA 2012) analyzed this algorithm and showed that on average it uses 1.9n ln n + O(n) comparisons to sort an input of size n, beating standard Quicksort, which uses 2n ln n + O(n) comparisons. We introduce a model that captures all dual-pivot algorithms, give a unified analysis, and identify new dual-pivot algorithms that minimize the average number of key comparisons among all possible algorithms up to a linear term. This minimum is 1.8n ln n + O(n). For the case that the pivots are chosen from a small sample, we include a comparison of dual-pivot Quicksort and classical Quicksort. Specifically, we show that dual-pivot Quicksort benefits from a skewed choice of pivots. We experimentally evaluate our algorithms and compare them to Yaroslavskiy's algorithm and the recently described three-pivot Quicksort algorithm of Kushagra et al. (ALENEX 2014).
Ralph Neininger - One of the best experts on this subject based on the ideXlab platform.
-
refined Quicksort asymptotics
Random Structures and Algorithms, 2015Co-Authors: Ralph NeiningerAbstract:The complexity of the Quicksort algorithm is usually measured by the number of key comparisons used during its execution. When operating on a list of n data, permuted uniformly at random, the appropriately normalized complexity Yn is known to converge almost surely to a non-degenerate random limit Y. This assumes a natural embedding of all Yn on one probability space, e.g., via random binary search trees. In this note a central limit theorem for the error term in the latter almost sure convergence is shown:n2lognYn-Yi¾?dNi¾?i¾?ni¾?∞,where N denotes a standard normal random variable. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 346-361, 2015
-
average case and distributional analysis of dual pivot Quicksort
ACM Transactions on Algorithms, 2015Co-Authors: Sebastian Wild, Markus E. Nebel, Ralph NeiningerAbstract:In 2009, Oracle replaced the long-serving sorting algorithm in its Java 7 runtime library by a new dual-pivot Quicksort variant due to Vladimir Yaroslavskiy. The decision was based on the strikingly good performance of Yaroslavskiy's implementation in running time experiments. At that time, no precise investigations of the algorithm were available to explain its superior performance—on the contrary: previous theoretical studies of other dual-pivot Quicksort variants even discouraged the use of two pivots. In 2012, two of the authors gave an average case analysis of a simplified version of Yaroslavskiy's algorithm, proving that savings in the number of comparisons are possible. However, Yaroslavskiy's algorithm needs more swaps, which renders the analysis inconclusive.To force the issue, we herein extend our analysis to the fully detailed style of Knuth: we determine the exact number of executed Java Bytecode instructions. Surprisingly, Yaroslavskiy's algorithm needs sightly more Bytecode instructions than a simple implementation of classic Quicksort—contradicting observed running times. As in Oracle's library implementation, we incorporate the use of Insertionsort on small subproblems and show that it indeed speeds up Yaroslavskiy's Quicksort in terms of Bytecodes; but even with optimal Insertionsort thresholds, the new Quicksort variant needs slightly more Bytecode instructions on average.Finally, we show that the (suitably normalized) costs of Yaroslavskiy's algorithm converge to a random variable whose distribution is characterized by a fixed-point equation. From that, we compute variances of costs and show that for large n, costs are concentrated around their mean.
-
average case and distributional analysis of dual pivot Quicksort
arXiv: Data Structures and Algorithms, 2013Co-Authors: Sebastian Wild, Markus E. Nebel, Ralph NeiningerAbstract:In 2009, Oracle replaced the long-serving sorting algorithm in its Java 7 runtime library by a new dual-pivot Quicksort variant due to Vladimir Yaroslavskiy. The decision was based on the strikingly good performance of Yaroslavskiy's implementation in running time experiments. At that time, no precise investigations of the algorithm were available to explain its superior performance - on the contrary: Previous theoretical studies of other dual-pivot Quicksort variants even discouraged the use of two pivots. Only in 2012, two of the authors gave an average case analysis of a simplified version of Yaroslavskiy's algorithm, proving that savings in the number of comparisons are possible. However, Yaroslavskiy's algorithm needs more swaps, which renders the analysis inconclusive. To force the issue, we herein extend our analysis to the fully detailed style of Knuth: We determine the exact number of executed Java Bytecode instructions. Surprisingly, Yaroslavskiy's algorithm needs sightly more Bytecode instructions than a simple implementation of classic Quicksort - contradicting observed running times. Like in Oracle's library implementation we incorporate the use of Insertionsort on small subproblems and show that it indeed speeds up Yaroslavskiy's Quicksort in terms of Bytecodes; but even with optimal Insertionsort thresholds the new Quicksort variant needs slightly more Bytecode instructions on average. Finally, we show that the (suitably normalized) costs of Yaroslavskiy's algorithm converge to a random variable whose distribution is characterized by a fixed-point equation. From that, we compute variances of costs and show that for large n, costs are concentrated around their mean.
-
average case and distributional analysis of java 7 s dual pivot Quicksort
2013Co-Authors: Sebastian Wild, Markus E. Nebel, Ralph NeiningerAbstract:In 2009, Oracle replaced the long-serving sorting algorithm in its Java 7 runtime library by a new dual pivot Quicksort variant due to Yaroslavskiy. The decision was based on the strikingly good performance of Yaroslavskiy’s implementation in running time experiments. At that time, no precise investigations of the algorithm were available to explain its superior performance — on the contrary: Previous theoretical studies of other dual pivot Quicksort variants even discouraged the use two pivots. Only in 2012, two of the authors gave an average case analysis of a simplified version of Yaroslavskiy’s algorithm, proving that savings in the number of comparisons are possible. However, Yaroslavskiy’s algorithm needs more swaps, which renders the analysis inconclusive. To force the issue, we herein extend our analysis to the fully detailed style of Knuth: We determine the exact number of executed Java Bytecode instructions. Surprisingly, Yaroslavskiy’s algorithm needs sightly more Bytecode instructions than a simple implementation of classic Quicksort — despite contradicting running times. Like in Oracle’s library implementation we incorporate the use of Insertionsort on small subarrays and show that it indeed speeds up Yaroslavskiy’s Quicksort in terms of Bytecodes. Even if using optimal Insertionsort thresholds the new Quicksort variant again needs slightly more Bytecode instructions on average. Finally, we show that the (suitably normalized) costs of Yaroslavskiy’s algorithm converge to a random variable whose distribution is characterized by a fix point equation. From that, we compute variances of costs and show that for large n, costs are concentrated about their mean.
-
refined Quicksort asymptotics
arXiv: Probability, 2012Co-Authors: Ralph NeiningerAbstract:The complexity of the Quicksort algorithm is usually measured by the number of key comparisons used during its execution. When operating on a list of $n$ data, permuted uniformly at random, the appropriately normalized complexity $Y_n$ is known to converge almost surely to a non-degenerate random limit $Y$. This assumes a natural embedding of all $Y_n$ on one probability space, e.g., via random binary search trees. In this note a central limit theorem for the error term in the latter almost sure convergence is shown: $$\sqrt{\frac{n}{2\log n}}(Y_n-Y) \stackrel{d}{\longrightarrow} {\cal N} \qquad (n\to\infty),$$ where ${\cal N}$ denotes a standard normal random variable.
Martin Aumuller - One of the best experts on this subject based on the ideXlab platform.
-
how good is multi pivot Quicksort
ACM Transactions on Algorithms, 2016Co-Authors: Martin Aumuller, Martin Dietzfelbinger, Pascal KlaueAbstract:Multi-Pivot Quicksort refers to variants of classical Quicksort where in the partitioning step k pivots are used to split the input into k + 1 segments. For many years, multi-pivot Quicksort was regarded as impractical, but in 2009 a two-pivot approach by Yaroslavskiy, Bentley, and Bloch was chosen as the standard sorting algorithm in Sun’s Java 7. In 2014 at ALENEX, Kushagra et al. introduced an even faster algorithm that uses three pivots. This article studies what possible advantages multi-pivot Quicksort might offer in general. The contributions are as follows: Natural comparison-optimal algorithms for multi-pivot Quicksort are devised and analyzed. The analysis shows that the benefits of using multiple pivots with respect to the average comparison count are marginal and these strategies are inferior to simpler strategies such as the well-known median-of-k approach. A substantial part of the partitioning cost is caused by rearranging elements. A rigorous analysis of an algorithm for rearranging elements in the partitioning step is carried out, observing mainly how often array cells are accessed during partitioning. The algorithm behaves best if three to five pivots are used. Experiments show that this translates into good cache behavior and is closest to predicting observed running times of multi-pivot Quicksort algorithms. Finally, it is studied how choosing pivots from a sample affects sorting cost. The study is theoretical in the sense that although the findings motivate design recommendations for multipivot Quicksort algorithms that lead to running-time improvements over known algorithms in an experimental setting, these improvements are small.
-
optimal partitioning for dual pivot Quicksort
ACM Transactions on Algorithms, 2015Co-Authors: Martin Aumuller, Martin DietzfelbingerAbstract: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. This can be done in different ways, giving rise to different algorithms. Recently, a dual-pivot algorithm due to Yaroslavskiy received much attention, because it replaced the well-engineered Quicksort algorithm in Oracle’s Java 7 runtime library. Nebel and Wild (ESA 2012) analyzed this algorithm and showed that on average it uses 1.9nln n + O(n) comparisons to sort an input of size n, beating standard Quicksort, which uses 2nln n + O(n) comparisons. We introduce a model that captures all dual-pivot algorithms, give a unified analysis, and identify new dual-pivot algorithms that minimize the average number of key comparisons among all possible algorithms up to a linear term. This minimum is 1.8nln n + O(n). For the case that the pivots are chosen from a small sample, we include a comparison of dual-pivot Quicksort and classical Quicksort. Specifically, we show that dual-pivot Quicksort benefits from a skewed choice of pivots. We experimentally evaluate our algorithms and compare them to Yaroslavskiy’s algorithm and the recently described 3-pivot Quicksort algorithm of Kushagra et al. (ALENEX 2014).
-
how good is multi pivot Quicksort
arXiv: Data Structures and Algorithms, 2015Co-Authors: Martin Aumuller, Martin Dietzfelbinger, Pascal KlaueAbstract:Multi-Pivot Quicksort refers to variants of classical Quicksort where in the partitioning step $k$ pivots are used to split the input into $k + 1$ segments. For many years, multi-pivot Quicksort was regarded as impractical, but in 2009 a 2-pivot approach by Yaroslavskiy, Bentley, and Bloch was chosen as the standard sorting algorithm in Sun's Java 7. In 2014 at ALENEX, Kushagra et al. introduced an even faster algorithm that uses three pivots. This paper studies what possible advantages multi-pivot Quicksort might offer in general. The contributions are as follows: Natural comparison-optimal algorithms for multi-pivot Quicksort are devised and analyzed. The analysis shows that the benefits of using multiple pivots with respect to the average comparison count are marginal and these strategies are inferior to simpler strategies such as the well known median-of-$k$ approach. A substantial part of the partitioning cost is caused by rearranging elements. A rigorous analysis of an algorithm for rearranging elements in the partitioning step is carried out, observing mainly how often array cells are accessed during partitioning. The algorithm behaves best if 3 to 5 pivots are used. Experiments show that this translates into good cache behavior and is closest to predicting observed running times of multi-pivot Quicksort algorithms. Finally, it is studied how choosing pivots from a sample affects sorting cost. The study is theoretical in the sense that although the findings motivate design recommendations for multipivot Quicksort algorithms that lead to running time improvements over known algorithms in an experimental setting, these improvements are small.
-
optimal partitioning for dual pivot Quicksort
International Colloquium on Automata Languages and Programming, 2013Co-Authors: Martin Aumuller, Martin DietzfelbingerAbstract: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. This can be done in different ways, giving rise to different algorithms. Recently, a dual pivot algorithm due to Yaroslavskiy received much attention, because it replaced the well-engineered Quicksort algorithm in Oracle's Java 7 runtime library. Nebel and Wild (ESA 2012) analyzed this algorithm and showed that on average it uses 1.9nln n+O(n) comparisons to sort an input of size n, beating standard Quicksort, which uses 2nln n+O(n) comparisons. We introduce a model that captures all dual pivot algorithms, give a unified analysis, and identify new dual pivot algorithms that minimize the average number of key comparisons among all possible algorithms up to lower order or linear terms. This minimum is 1.8n ln n+O(n).
-
optimal partitioning for dual pivot Quicksort
arXiv: Data Structures and Algorithms, 2013Co-Authors: Martin Aumuller, Martin DietzfelbingerAbstract: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. This can be done in different ways, giving rise to different algorithms. Recently, a dual-pivot algorithm proposed by Yaroslavskiy received much attention, because a variant of it replaced the well-engineered Quicksort algorithm in Sun's Java 7 runtime library. Nebel and Wild (ESA 2012) analyzed this algorithm and showed that on average it uses 1.9n ln n + O(n) comparisons to sort an input of size n, beating standard Quicksort, which uses 2n ln n + O(n) comparisons. We introduce a model that captures all dual-pivot algorithms, give a unified analysis, and identify new dual-pivot algorithms that minimize the average number of key comparisons among all possible algorithms up to a linear term. This minimum is 1.8n ln n + O(n). For the case that the pivots are chosen from a small sample, we include a comparison of dual-pivot Quicksort and classical Quicksort. Specifically, we show that dual-pivot Quicksort benefits from a skewed choice of pivots. We experimentally evaluate our algorithms and compare them to Yaroslavskiy's algorithm and the recently described three-pivot Quicksort algorithm of Kushagra et al. (ALENEX 2014).
