Sorting Algorithms in Java

Arrays.sort(Object[]) and Collections.sort() use Tim Sort (stable). Arrays.sort(int[]) and other primitive overloads use Dual-Pivot Quick Sort, which is faster for primitives where stability is irrelevant. Use a Comparator for custom orderings.

Objects need stability for correct multi-key sorting, so Java uses stable Tim Sort. Primitives have no identity beyond their value, so stability is meaningless — and Dual-Pivot Quick Sort partitions around two pivots for excellent cache performance. See what algorithm Java uses for the details.

void quickSort(int[] a, int lo, int hi) {
    if (lo < hi) {
        int p = partition(a, lo, hi);
        quickSort(a, lo, p - 1);
        quickSort(a, p + 1, hi);
    }
}

Java is the clearest example of a standard library deliberately using two different sorting algorithms and choosing between them based on what you are sorting. Which one you get depends entirely on whether you pass objects or primitives.

Objects — Arrays.sort(Object[]) and Collections.sort() — use Tim Sort. Since Java 7 this has been a port of the same adaptive Merge Sort hybrid that Python uses. It is stable, which is essential for objects: if you sort a list of employees by name and then by department, stability is what keeps each department's employees alphabetical. It costs O(n) auxiliary memory, which is considered an acceptable price for objects since you are already paying for references and heap allocation.

Primitives — Arrays.sort(int[]) and friends — use dual-pivot Quick Sort. Contributed by Vladimir Yaroslavskiy in Java 7, this partitions around two pivots into three regions rather than one pivot into two. That produces shallower recursion and better cache behaviour than classic Quick Sort, and it measurably outperformed the previous implementation.

Why the split? Because stability is meaningless for primitives. Two int values of 42 are indistinguishable, so there is no original order worth preserving — which means Java can take the faster, unstable, in-place algorithm and lose nothing at all. For objects, where two "equal" items can differ in every other field, stability is worth the memory.

Modern JDKs have hardened the primitive path further: it uses Insertion Sort below a small threshold, and newer versions detect pathological input and fall back to Heap Sort so that the worst case cannot degrade to O(n²).