Dual-Pivot Quick Sort
- Ω( n log n )
- Θ( n log n )
- O( n2 )
- space O( log n )
Array
Comparator strip
Index down, time to the right
- Comparisons count only element-against-element checks; loop and index checks are never counted.
- Reads and writes include reads and writes to helper buffers (merge, counting, radix, bucket and tim sort).
- A swap counts once, as a swap. It is never also counted as a read or a write.
- Real time is the average time of the counted sort on this device over repeated runs, measured once before playback and independent of animation speed. Visual time is the time spent animating, excluding pauses.
How dual-pivot quick sort works
Dual-pivot quick sort, by Vladimir Yaroslavskiy, partitions around two pivots into three parts: smaller than the first pivot, between the two, and larger than the second.
Read more
Three parts per pass means fewer passes over the data and fewer cache misses. A variant of this algorithm is what Java uses for sorting primitive arrays. The pivots here are picked deterministically from the one-third and two-thirds positions.
| Best time | Ω( n log n ) | good |
|---|---|---|
| Average time | Θ( n log n ) | good |
| Worst time | O( n2 ) | poor |
| Worst space | O( log n ) | good |
Big O notation gives the lower, average and upper bounds of an algorithm. Time complexity bounds the number of operations; space complexity bounds the extra memory it uses.