# Quicksort dual pivot or single

I've seen to explanations for the quick sort algorithm.

One in which a pivot is chosen, and put into place, before both sides of the pivot are recursively pivot-sorted.

Another involved a more complicated solution involving two pivots which interchanged.

What are the benefits of either solution, why was the dual-pivot solution created? Is it faster?

Basically Dual-pivot Quicksort buys you two items: The best case running time is $\Theta(n \log_3 n)$ instead of $\Theta(n \log_2 n)$ since each partition is the third part of the entire current range. Also, if one pivot is not good (it is close to one of the ends of the current range), there is a good chance that the second pivot will be better.

• I looked further into it, and the dual pivot system seems to just be a (complicated-looking) way of partitioning the array with O(n) time-complexity.
– Tobi
Jun 18, 2017 at 21:38
• They weren't actually pivots, but pointers. Unless I'm mistaken and have come across a 3rd type of implementation/explanation
– Tobi
Jun 18, 2017 at 21:43
• $\Theta(n \log_3 n)$ is the same thing as $\Theta(n \log_2 n)$. Jun 18, 2017 at 21:51
• @Gilles Yes, but the point is that if the partitioning routine splits evenly, the recursion depth is smaller than in single-pivot quicksort. Jun 18, 2017 at 22:03
• @Gilles Dual-pivot quicksort made it in JDK 7. I am rather confident that they actually benchmarked it against single-pivot version. Jun 18, 2017 at 22:17

This is a visualization of the algorithm. And this is claim

This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

• From your link with the claim: "Choose two pivot elements P1 and P2. We can get, for example, the first element a[left] as P1 and the last element a[right] as P2.". Well, that's stupid because it means sorting a sorted array will take quadratic time. Jun 19, 2017 at 11:09
• Sorted array is just one possibility out of thousands or millions possible permutations. In any case, it claims that "... O(n log(n)) performance on MANY DATA SETS that cause other quicksorts to degrade...". Theoretically, however you shuffle data, there is always a chance of ending up with sorted array unless you check the array is already sorted before you invoke quicksort. Jun 19, 2017 at 11:24