Java 8: How does `QUICKSORT_THRESHOLD=286` comes from?

Question

In Java 8, function Arrays.sort() depends on the length of array;

if(length>=`QUICKSORT_THRESHOLD=286`){
    take `Dual-Pivot Quicksort`;
}
else if(length<`QUICKSORT_THRESHOLD=286` && length>`INSERTION_SORT_THRESHOLD=47`){
    take `One-Pivot Quicksort
}
else { take `Insertion Sort`}

How does the 286 or 47 comes from?

A heck of a lot of performance tests probably. – Tunaki Mar 16 '16 at 13:13 — Tunaki, Mar 16 '16 at 13:13

score 1 · Accepted Answer · edited May 23 '17 at 12:23

1

This is based on the calculation of the complexity of the algorithm.

Some infos here on StackOverflow: How to optimize quicksort

Merge sort: https://www.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/analysis-of-merge-sort

Quick sort: https://www.khanacademy.org/computing/computer-science/algorithms/quick-sort/a/analysis-of-quicksort

edited May 23 '17 at 12:23

Community

1
1

answered Mar 16 '16 at 13:19

Simon Martinelli

34,053
5
48
82

score 1 · Answer 2 · answered Mar 16 '16 at 13:41

Insertion sort is faster than quick sort for smaller arrays because there are less constant-factor overheads involved. Same with the single-pivot vs dual-pivot. We need to find out at what point this is to get these numbers.

They probably tried a range of numbers and then ran performance tests for each of them, and kept the numbers with the best performance.

Java 8: How does `QUICKSORT_THRESHOLD=286` comes from?

2 Answers2