loading...
Cover image for Dual Pivot Quick Sort: Java’s default sorting algorithm for primitive data types.

Dual Pivot Quick Sort: Java’s default sorting algorithm for primitive data types.

s_awdesh profile image Awdesh Updated on ・3 min read

What happens when we do Arrays.sort() in Java? which sorting algorithm does Java use in the background?

Since Java 7 release back in 2011, default sorting algorithm used is DualPivotQuickSort which is an enhancement over classic quicksort algorithm.

Dual pivot quicksort is a combination of insertion sort and quick sort. Insertion sort has faster runtime when the number of elements to be sorted is small, Double pivot quicksort uses this fact thus when the number of elements is <= 47 Java performs insertion sort under the hood.

When input size array is larger than 47 Java uses Double pivot quicksort. As the name suggests DualPivotQuickSort algorithm picks 2 pivots instead of 1. Unlike quicksort in which we partition the array around 1 pivot, we partition the array in three parts around 2 pivots.

1st sub array : items < LP
2nd sub array : LP <= items <= RP
3rd sub array =: items >= RP

Algorithm

LP: Left Pivot
RP: Right Pivot

1.) Left most item in an array is taken as the left pivot and Rightmost item as the right pivot.
2.) Swap Left pivot with Right Pivot if LP > RP
3.) Partition array in three sub-arrays around left and right pivot.

Once a partition is done we perform above 3 steps recursively on three sub-array.

Let’s walk through an example-:

Alt text of image

No need to swap pivots in above image since LP < RP.
Now we partition the array following below schemes.

1st sub array : items < LP
2nd sub array : LP <= items <= RP
3rd sub array =: items >= RP

Alt text of image

Now we have 3 sub-array over which we'll perform the same steps as above. Since the first two arrays have only 2 items, one will become left pivot and other will become right pivot. We'll swap left pivot with right pivot if the left pivot is greater than right pivot which is not the case for first two sub-arrays.

Alt text of image

For the third sub-array as we can see in below image left pivot is greater than right pivot thus we'll swap them.

Alt text of image

Swapping pivots.
Alt text of image

We don't have any more elements in the array that we can partition further.
Alt text of image

Alt text of image

References

https://www.geeksforgeeks.org/dual-pivot-quicksort/
https://stackoverflow.com/questions/20917617/whats-the-difference-of-dual-pivot-quick-sort-and-quick-sort
http://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf

Conclusion
Similarly, Python uses Timsort which is a combination of insertion sort and merge sort. I’d like to read and write about different other variation of quicksort in the next few days.


If you want me to write on a specific topic, please feel free to post them in the comment section below.

You can support my work by buying me a coffee below. 💚💚💚💚💚💚 !!
Buy me a ko-fi

Posted on by:

s_awdesh profile

Awdesh

@s_awdesh

Learner, philomath. Engineer by choice humorous by nature.

Discussion

pic
Editor guide
 

Regarding the number of elements are <= 47, does this only happen if the whole array .sort() is called on is <= 47, or does the DualPivotQuickSort algorithm use Insertion Sort to sort partitions of length <= 47 instead of recursing DPQS on it??

 

DualPivotQuickSort class has a threshold of '47' defined for number of elements in an array. If number of elements are lesser than threshold then sorting function uses insertion sort.

Below snippet is from Java docs.

private static final int INSERTION_SORT_THRESHOLD = 47;

// Use insertion sort on tiny arrays
 if (length < INSERTION_SORT_THRESHOLD) {
        if (leftmost) {
              ...
              ...
 

Yeah, but, is this inside or outside the function that recurses?

function DualPivotQuickSort(arr) {
  if (length < INSERTION_SORT_THRESHOLD) { }
  else {
    /* ... */
    [slice1, slice2, slice3].map(DualPivotQuickSort)
  }
}
// vs
function DualPivotQuickSort(arr) {
  if (length < INSERTION_SORT_THRESHOLD) { }
  else {
    function realDPQS(a) {
      /* ... */
      [slice1, slice2, slice3].map(realDPQS)
    }
  }
}
 

Excellent explanation! This is perhaps my favorite sorting algorithm out there -- I've been studying it on and off for a few years now.

 

Awesome visual explainer on this algorithm!

 

Really like the way you explained all the steps using a deck of cards!

 

Whats the reason of different languages choosing different sorts? Whats the logic behind that?

Loved the deck approach, nice read!

 

an article on dev.to without any code ? ;)

 

I think there's a correction on the fourth picture (third sub-array). It should be, "Since LP > RP, Swap (LP,RP)".

I also do love that you used cards as a visual explanation. Nice one!!

 

Good catch. I've updated the image now.