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

View post

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