DEV Community

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

Awdesh on July 29, 2018

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, defaul...

Read full post

Mihail Malo • Aug 7 '18

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??

Awdesh • Aug 8 '18 • Edited

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) {
              ...
              ...

Mihail Malo • Aug 8 '18

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)
    }
  }
}