Hybrid and library sorting

Recursion has overhead: function calls, bounds checks, and partitions or merges that are not worth setting up on a few elements. Below a small size, insertion sort is faster than recursing further, even though it is O(n²), because for tiny n its tiny constant factors win.

Hybrid sorts stop recursing once a subarray falls under a threshold of a few dozen elements and finish it with insertion sort. The best threshold depends on the hardware and element type, so libraries tune it by measurement.

1static void hybridMergeSort(int[] arr, int[] buf, int lo, int hi) {
2    if (hi - lo + 1 <= 32) {            // threshold: tune by benchmarking
3        insertionSort(arr, lo, hi);
4        return;
5    }
6    int mid = lo + (hi - lo) / 2;
7    hybridMergeSort(arr, buf, lo, mid);
8    hybridMergeSort(arr, buf, mid + 1, hi);
9    merge(arr, buf, lo, mid, hi);
10}

Introsort (introspective sort) starts as quick sort but counts the recursion depth. If it exceeds about 2·log₂ n, the partitions are clearly unbalanced, so it switches to heap sort for that subarray. Small subarrays are finished with insertion sort.

The result is quick sort's speed on typical data with a guaranteed O(n log n) worst case. It is used by C++'s std::sort. Java does not use introsort for objects, but recent versions of the primitive sort include similar safeguards against quadratic behaviour.

TimSort, created for Python and used by Java for objects, is a stable, adaptive merge sort. It scans the array for natural runs, which are already ascending or strictly descending stretches (descending runs are reversed), extends short runs to a minimum length with binary insertion sort, and merges runs while keeping run lengths balanced on a stack.

When one run keeps winning during a merge, it switches to galloping mode and uses exponential search to jump ahead. On already sorted or nearly sorted data it runs in close to O(n); in the worst case it is O(n log n). It needs up to n/2 extra space.

Arrays.sort(int[]) and the other primitive overloads use a Dual-Pivot Quicksort. It partitions into three parts with two pivots and switches to insertion sort or merging of runs where that is cheaper. Since equal primitives are indistinguishable, stability does not matter, so a faster unstable algorithm is acceptable.

Sort a range with Arrays.sort(arr, from, toExclusive). For descending order, sort ascending and reverse, or box into Integer[] and pass Comparator.reverseOrder().

1int[] a = {5, 2, 9, 1, 7};
2Arrays.sort(a);                         // [1, 2, 5, 7, 9]
3Arrays.sort(a, 1, 4);                   // sort only indices 1..3
4
5Integer[] boxed = {5, 2, 9, 1, 7};
6Arrays.sort(boxed, Comparator.reverseOrder());   // [9, 7, 5, 2, 1]

Arrays.sort(Object[]), Arrays.sort(T[], Comparator), Collections.sort and List.sort use TimSort. They are stable, so sorting by one key and then another works as expected.

The comparator must be consistent: compare(a, b) and compare(b, a) must have opposite signs, and it must be transitive. A broken comparator can make TimSort throw IllegalArgumentException: Comparison method violates its general contract!. Never compute a - b for ints, since it can overflow.

1record Person(String name, int age) {}
2
3List<Person> people = new ArrayList<>(list);
4people.sort(Comparator.comparingInt(Person::age)
5                      .thenComparing(Person::name));   // sort by age, then name
6
7// Broken: overflows for extreme values and violates the contract
8// people.sort((a, b) -> a.age() - b.age());

Arrays.parallelSort splits the array into chunks, sorts them on the common ForkJoin pool, and merges the results. For arrays below a small threshold (a few thousand elements) it falls back to the sequential sort.

It helps on large arrays when several CPU cores are free. The gain is bounded by the memory-bound merge steps, so expect a good speedup but not one proportional to the core count. Measure with JMH before relying on it.

1int[] big = new Random(1).ints(5_000_000).toArray();
2Arrays.parallelSort(big);                     // uses ForkJoinPool.commonPool()