Advanced sorting: Shell sort, quicksort and radix sort

← Back to the section

Simple sorts run in O(N²) and are hopelessly slow on large data. Merge sort already gives O(N·log N), but it needs twice the memory. Here are the algorithms that sort just as fast (or nearly) without wasting memory: Shell sort, quicksort and the rather unusual radix sort.

Shell sort

Shell sort is a clever add-on over insertion sort. Recall the weak spot of insertions: a small element sitting at the end has to be dragged to the front one position at a time, shifting everyone along the way — many tiny moves.

Shell's idea: first establish a rough order with long jumps, and only then a precise one. The algorithm applies insertion sort not to neighbours but to elements standing h apart ("h-sorting"): such jumps quickly pull distant elements close to where they belong. Then h is reduced and the pass repeats, until h = 1 — ordinary insertions. By then the array is almost ordered, and on such data insertions run in nearly O(N).

The sequence of gaps h is chosen so that passes don't repeat each other's work; a popular variant (Knuth's) is 1, 4, 13, 40, 121, … — each next one is h = 3·h + 1.

live example

import java.util.Arrays;

public class ShellDemo {
    public static void main(String[] args) {
        int[] a = {62, 83, 18, 53, 7, 17, 95, 86, 47, 69};
        int moves = 0, h = 1;
        while (h <= a.length / 3) h = h * 3 + 1;
        while (h > 0) {
            for (int i = h; i < a.length; i++) {
                int tmp = a[i], j = i;
                while (j >= h && a[j - h] > tmp) { a[j] = a[j - h]; j -= h; moves++; }
                a[j] = tmp;
            }
            System.out.println("h = " + h + ": " + Arrays.toString(a));
            h = (h - 1) / 3;
        }
        System.out.println("moves in total: " + moves);
    }
}

The first line of the output is the state after the pass with h = 4: the array is not sorted yet, but the large-scale disorder is gone, and the h = 1 pass has little left to do. That is where the gain comes from: on these same ten numbers plain insertions make 21 moves, Shell sort 11.

Quicksort

Quicksort is the most popular general-purpose sorting algorithm. On average it is O(N·log N), and it usually outruns every rival. At its core lies the partition operation.

Partitioning picks some pivot value and rearranges the array so that everything smaller than the pivot ends up on the left and everything larger on the right. The pivot itself lands exactly on its final place — the boundary between the groups. Inside the groups the order is still arbitrary.

Then comes the recursion in the divide-and-conquer spirit: the same trick is applied to the left and right groups, to their subgroups and so on, until the groups shrink to a single element. Once every tiny subarray is ordered, the whole array is ordered.

Let's count the comparisons on shuffled and on already ordered data:

live example

import java.util.Arrays;

public class QuickDemo {
    static int comparisons = 0;

    static void quickSort(int[] a, int left, int right) {
        if (right <= left) return;
        int p = partition(a, left, right);
        quickSort(a, left, p - 1);
        quickSort(a, p + 1, right);
    }

    static int partition(int[] a, int left, int right) {
        int pivot = a[right], i = left;
        for (int j = left; j < right; j++) {
            comparisons++;
            if (a[j] < pivot) swap(a, i++, j);
        }
        swap(a, i, right);
        return i;
    }

    static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

    public static void main(String[] args) {
        int[] mixed = {3, 8, 2, 7, 1, 6, 5, 4};
        quickSort(mixed, 0, 7);
        System.out.println("shuffled: " + Arrays.toString(mixed) + ", comparisons " + comparisons);
        comparisons = 0;
        quickSort(new int[]{1, 2, 3, 4, 5, 6, 7, 8}, 0, 7);
        System.out.println("already ascending: comparisons " + comparisons);
    }
}

The Achilles heel. Speed depends on how evenly the pivot splits the array. Split it in half — you get log N levels and O(N·log N). The example shows the opposite case too: 14 comparisons on shuffled numbers and 28 on ordered ones, exactly N·(N−1)/2. The pivot here is the last element, so on sorted data it is the largest every time, the partition peels off one element per level, the number of levels becomes N — and the algorithm degenerates into O(N²), slower than the simple sorts.

The cure is to choose the pivot with some thought. A common trick is the median of three: take the first, the middle and the last elements and make the middle one by value the pivot. That practically rules out the degenerate cases and simplifies the partition code as a bonus. For very small subarrays implementations often switch to insertion sort — on a dozen elements it is faster because of lower overhead.

Radix sort

Every algorithm above compares elements with one another. Radix sort takes a fundamentally different route: it never compares elements, it distributes them by digits.

Here is how it works for numbers: look at the last digit of every number and drop the numbers into ten "buckets" (0–9) in order of appearance, then collect the buckets back into the array. Repeat for the tens, then the hundreds — up to the highest digit, after which the array is sorted. The whole thing rests on the distribution being stable: numbers sharing a digit keep the order established by the previous passes.

Working without comparisons, radix sort beats the N·log N barrier. The exact estimate is O(d · N), where d is the number of digits in the key: that is how many passes over the array it makes. When the key width is fixed — say, every number fits into four bytes — d becomes a constant and the time becomes linear; hence the familiar "O(N)". If the keys are long and of varying length, the factor d stops being a detail. There is a second price as well: it applies only to data that decomposes into digits (integers, fixed-length strings), and it needs extra memory for the buckets. The tool is not universal but specialized — and unbeatable on its own data.

Which one to pick

• Quicksort — the default for large general-purpose arrays, with pivot protection such as the median of three.
• Shell sort — mid-sized data where simple code matters; no extra memory.
• Merge sort — when you need a guaranteed O(N·log N) with no risk of degeneration and can spare the memory.
• Radix sort — large volumes of integers or short strings of equal length.

How it is done in Java

Hardly anyone writes their own quicksort in production code: Arrays.sort is already tuned and handles degenerate cases better than a homemade one. There is one thing worth knowing about it: two different algorithms hide behind that single name, and the choice is made by data type.

For primitives (int[], long[], double[]) it is a dual-pivot quicksort — the JDK class is literally called DualPivotQuicksort. It is the same partitioning scheme as above, only with two pivots, cutting the array into three parts instead of two: below the first pivot, between the pivots, above the second. O(N·log N) on average, and almost no extra memory. There is a safeguard against degenerating into O(N²): since Java 14, if the recursion goes suspiciously deep — a sure sign that the pivots keep coming out badly — the library switches to heapsort with its guaranteed O(N·log N). And the shortest stretches, as usual, are finished off with insertions.

For objects (Arrays.sort(T[], Comparator), Collections.sort, list.sort(...)) it is TimSort: merging plus insertions. It is stable, it looks for already ordered runs in the data, and on nearly sorted input it approaches O(N). The price is memory: it needs a temporary array of up to half the original size.

The split is not accidental. Among primitives equal values are indistinguishable, so stability there means nothing — which allows the faster and more memory-frugal quicksort. Among objects two elements with the same key still differ in everything else, and the order between them matters — hence merging, which gives stability for free.

There is also Arrays.parallelSort: the same idea, but the chunks are sorted in several threads and then merged. The gain shows up only on genuinely large arrays: on small ones handing out the work eats it all.

A trap. Arrays.sort(int[]) takes no comparator: primitives are sorted ascending and no other way. To get descending order you have to wrap the numbers into objects:

live example

import java.util.Arrays;
import java.util.Comparator;

public class ReverseDemo {
    public static void main(String[] args) {
        Integer[] ids = {5, 2, 9};
        Arrays.sort(ids, Comparator.reverseOrder());
        System.out.println(Arrays.toString(ids));
    }
}

And that is an entirely different price: instead of a dense array of numbers, an array of references to objects; instead of quicksort, TimSort with its temporary array. On large volumes it is cheaper to sort the int[] as it is and reverse the result in a single pass.

In short

• Shell sort — insertions with long jumps: it sorts elements h apart, gradually shrinking h down to 1. Simple, no extra memory, good for mid-sized arrays.
• Quicksort — recursive partitioning around a pivot; O(N·log N) on average, the fastest in practice. It degenerates into O(N²) when the pivot keeps turning out to be an extreme value (28 comparisons instead of 14 on eight ordered numbers); the median of three saves it.
• Radix sort — no comparisons, distribution by digits; O(d · N), that is linear for a short key, and only for numbers or strings, at the cost of extra memory.
• The growth rate O(N·log N) is the practical ceiling for comparison sorts; only specialized methods such as radix sort go faster.
• In Java Arrays.sort is two algorithms: DualPivotQuicksort for primitives (fast, not stable) and TimSort for objects (stable, at the cost of a temporary array).

What to read next

• Binary trees — the fast lookup of an ordered array plus the fast insertion of a list.
• Heaps — that very heapsort, the safeguard Arrays.sort falls back on.
• Simple sorting — the insertions that Shell sort grew out of.
• Recursion — divide and conquer, and merge sort.