Understanding Java’s TimSort and Dual‑Pivot Quicksort: How They Work and Perform

Introduction

Sorting is a routine task for Java developers, and the JDK provides rich APIs for it. A good sorting method must be generic, efficient, and practical, balancing time and space complexity while preserving stability. This article focuses on the algorithms behind Java’s sorting methods and highlights the ones worth learning.

Case Study

Typical usage of Java 8 streams to sort a list:

<span>List<Integer> list = Arrays.asList(10, 50, 5, 14, 16, 80);</span>
<span>System.out.println(list.stream().sorted().collect(Collectors.toList()));</span>

During execution, SortedOps.java calls Arrays.sort(array, 0, offset, comparator), which invokes the array‑based sort algorithm.

<span>@Override</span>
<span>public void end() {</span>
<span>    Arrays.sort(array, 0, offset, comparator);</span>
<span>    downstream.begin(offset);</span>
<span>    if (!cancellationWasRequested) {</span>
<span>        for (int i = 0; i < offset; i++)</span>
<span>            downstream.accept(array[i]);</span>
<span>    } else {</span>
<span>        for (int i = 0; i < offset && !downstream.cancellationRequested(); i++)</span>
<span>            downstream.accept(array[i]);</span>
<span>    }</span>
<span>    downstream.end();</span>
<span>    array = null;</span>
<span>}</span>

Using Collections.sort() produces the same result as list.stream().sorted() because both delegate to Arrays.sort for the underlying array.

<span>List<Integer> list1 = Arrays.asList(10, 50, 5, 14, 16, 80);</span>
<span>System.out.println(list1.stream().sorted().collect(Collectors.toList()));</span>
<span>List<Integer> list2 = Lists.newArrayList();</span>
<span>list2.addAll(list1);</span>
<span>Collections.sort(list2);</span>
<span>System.out.println(list2);</span>
<span>// Output:</span>
<span>// [5, 10, 14, 16, 50, 80]</span>
<span>// [5, 10, 14, 16, 50, 80]</span>

Collections.sort Method

The JDK defines Collections.sort as:

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    list.sort(null);
}

Javadoc notes:

1. Sorts the specified list into ascending order, according to the Comparable natural ordering of its elements.
2. This sort is guaranteed to be stable; equal elements will not be reordered as a result of the sort.
3. The specified list must be modifiable, but need not be resizable.

Internally, List.sort converts the list to an Object[] and calls Arrays.sort to avoid the O(n² log n) cost of sorting a linked list in place.

default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

The Javadoc explains that converting to an array prevents the quadratic performance that would arise from sorting a linked list directly.

TimSort Algorithm

TimSort is an adaptive, hybrid, stable sorting algorithm invented by Tim Peter in 2002. It originated in Python and is now used in Java, Android, and many other platforms. Java switched from a plain merge sort to TimSort in JDK 1.7 for reference‑type collections.

Complexity: average and worst O(n log n), best O(n); space O(n). The algorithm is stable.

Core Idea of TimSort

For runs shorter than 64 (Java uses 32), TimSort applies binary insertion sort. The algorithm assumes real data often contains partially ordered runs. A run is a maximal monotonic (ascending or descending) subsequence; minrun is the minimum run length (typically 32‑64). The list is divided into runs, and short runs are extended to at least minrun by inserting elements.

Example: with minrun = 3, the sequence [5, 2, 8, 5, 7, 23, 45, 63] yields runs [2,5,8] and [5,7,23,45,63], which are then merged.

Runs are merged using a stack. Two conditions trigger a merge:

x1 ≤ x2 + x3

x1 ≤ x2

These rules keep merge sizes balanced.

TimSort Java Source

Key parts of the implementation (simplified):

static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,
                     T[] work, int workBase, int workLen) {
    int nRemaining = hi - lo;
    if (nRemaining < 2) return;
    if (nRemaining < MIN_MERGE) {
        int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
        binarySort(a, lo, hi, lo + initRunLen, c);
        return;
    }
    TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen);
    int minRun = minRunLength(nRemaining);
    do {
        int runLen = countRunAndMakeAscending(a, lo, hi, c);
        if (runLen < minRun) {
            int force = nRemaining <= minRun ? nRemaining : minRun;
            binarySort(a, lo, lo + force, lo + runLen, c);
            runLen = force;
        }
        ts.pushRun(lo, runLen);
        ts.mergeCollapse();
        lo += runLen;
        nRemaining -= runLen;
    } while (nRemaining != 0);
    ts.mergeForceCollapse();
}

private static int minRunLength(int n) {
    int r = 0; // becomes 1 if any 1 bits are shifted off
    while (n >= MIN_MERGE) {
        r |= (n & 1);
        n >>= 1;
    }
    return n + r;
}

private void pushRun(int runBase, int runLen) {
    this.runBase[stackSize] = runBase;
    this.runLen[stackSize] = runLen;
    stackSize++;
}

private void mergeCollapse() {
    while (stackSize > 1) {
        int n = stackSize - 2;
        if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
            if (runLen[n-1] < runLen[n+1]) n--;
            mergeAt(n);
        } else if (runLen[n] <= runLen[n+1]) {
            mergeAt(n);
        } else {
            break;
        }
    }
}

The merge step uses a “gallop” mode to skip already‑ordered portions, reducing the amount of data copied.

Dual‑Pivot Quicksort

For primitive arrays, Java delegates to DualPivotQuicksort. The algorithm selects two pivots, dividing the array into three (effectively four) regions and recursively sorting each.

public static void sort(int[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}

Core Idea

Two pivots create the following partitions: ≤ pivot1, between pivot1 and pivot2, and ≥ pivot2. The algorithm recursively processes the middle region while shrinking the unsorted portion. This approach yields better performance than classic single‑pivot quicksort on many data sets.

static void sort(int[] a, int left, int right,
                 int[] work, int workBase, int workLen) {
    if (right - left < QUICKSORT_THRESHOLD) {
        sort(a, left, right, true);
        return;
    }
    // ... detection of runs, merging, and recursive calls ...
}

The implementation also falls back to insertion sort for small sub‑arrays and may use merge‑like steps for stability.

Performance Comparison

A benchmark on a single machine sorted 100 million random integers (range 0‑100 000 000) using three algorithms. Times are in milliseconds.

Algorithm

QuickSort

Merge Sort

Dual‑Pivot QuickSort

Average

19232

27760

16867

The results show Dual‑Pivot Quicksort consistently outperforms the other two methods on this data set.

Conclusion

Java’s sorting APIs hide sophisticated algorithms such as TimSort and Dual‑Pivot Quicksort. Understanding their inner workings helps developers appreciate why the JDK chooses hybrid strategies and can guide performance‑critical code. The same principle appears in other data structures (e.g., HashMap’s switch from linked list to red‑black tree), illustrating the value of adaptive, mixed‑algorithm designs.