Sorting

Sorting is the most studied problem in computing, and for good reason: sorted data makes searching, de-duplicating, merging and reporting cheap. In CPS 1231 you wrote selection and bubble sort; this chapter explains why nobody uses them for large inputs, how the fast algorithms work, when you can beat O(n log n), and why you cannot beat it with comparisons alone.

Two words appear in every section, so learn them now:

• Stable: equal elements stay in the same order as in the input.
• In place: the sort needs only O(1) extra memory besides the array (a few variables, not a second array).

The simple sorts, recalled

You already know these three. What matters now is how they compare.

Algorithm	Best	Average	Worst	Stable?	In place?
Selection sort	O(n²)	O(n²)	O(n²)	No	Yes
Bubble sort (with early exit)	O(n)	O(n²)	O(n²)	Yes	Yes
Insertion sort	O(n)	O(n²)	O(n²)	Yes	Yes

Selection sort always scans the whole unsorted part, so even a sorted array costs n(n−1)/2 comparisons. Its long-distance swap is also what makes it unstable. Of the three, only insertion sort earns a place in real libraries.

Insertion sort, and why it loves nearly-sorted data

Insertion sort grows a sorted prefix a[0..i-1] and inserts a[i] into it by shifting larger elements one place right:

static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int key = a[i];               // the element to insert
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];          // shift the larger element one place right
            j--;
        }
        a[j + 1] = key;               // drop the key into the gap
    }
}

Worked example on [5, 2, 4, 6, 1, 3]. The "sorted hand" is the prefix a[0..i] after each step.

i	key	what happens	sorted hand	not yet looked at	shifts
start		only 5 is in the hand	5	2, 4, 6, 1, 3
1	2	5 > 2, shift 5 right; put 2 at index 0	2, 5	4, 6, 1, 3	1
2	4	5 > 4, shift 5; 2 < 4, stop; put 4 at index 1	2, 4, 5	6, 1, 3	1
3	6	5 < 6, stop at once: 6 stays	2, 4, 5, 6	1, 3	0
4	1	6, 5, 4, 2 are all > 1: shift all four; put 1 at index 0	1, 2, 4, 5, 6	3	4
5	3	shift 6, 5, 4; 2 < 3, stop; put 3 at index 2	1, 2, 3, 4, 5, 6	(none)	3

Total: 9 shifts. The input has exactly 9 inversions — that is not a coincidence.

An inversion is a pair of positions i < j with a[i] > a[j] (two elements in the wrong order). Every shift in the inner loop removes exactly one inversion, and nothing else happens in that loop. So insertion sort runs in O(n + I) time, where I is the number of inversions:

• sorted input: I = 0, so n − 1 comparisons and no shifts: O(n);
• reverse-sorted input: I = n(n−1)/2: O(n²);
• "nearly sorted" input, where every element is at most k places from its final position: an element can only be inverted with elements fewer than 2k places away, so I < 2nk and the time is O(nk) — linear for a small constant k.

For example, [1, 3, 2, 4, 6, 5] has only 2 inversions (3 > 2 and 6 > 5), and insertion sort finishes it with just 2 shifts.

That is why production sorts (TimSort, Java's quick sort) switch to insertion sort for short ranges of a few dozen elements: on tiny or nearly-sorted arrays its low overhead beats any O(n log n) algorithm.

Merge sort

Merge sort is divide-and-conquer in its purest form: split the array in half, sort each half recursively, then merge the two sorted halves. In Chapter 7 you solved its recurrence T(n) = 2T(n/2) + Θ(n) = Θ(n log n). Here is the implementation.

public static void mergeSort(int[] a) {
    int[] tmp = new int[a.length];    // one scratch array, allocated once
    mergeSort(a, tmp, 0, a.length - 1);
}

private static void mergeSort(int[] a, int[] tmp, int lo, int hi) {
    if (lo >= hi) return;             // 0 or 1 element: already sorted
    int mid = (lo + hi) >>> 1;        // unsigned shift: no overflow
    mergeSort(a, tmp, lo, mid);
    mergeSort(a, tmp, mid + 1, hi);
    merge(a, tmp, lo, mid, hi);
}

private static void merge(int[] a, int[] tmp, int lo, int mid, int hi) {
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];   // <= : ties go left, so the sort is stable
        else              tmp[k++] = a[j++];
    }
    while (i <= mid) tmp[k++] = a[i++];        // copy whichever half is left over
    while (j <= hi)  tmp[k++] = a[j++];
    for (k = lo; k <= hi; k++) a[k] = tmp[k];
}

One merge, step by step. Merge the left half [2, 5, 8] with the right half [1, 5, 9]:

step	compare	take	output so far
1	2 vs 1	1 (right)	[1]
2	2 vs 5	2 (left)	[1, 2]
3	5 vs 5	5 (left — a tie goes left)	[1, 2, 5]
4	8 vs 5	5 (right)	[1, 2, 5, 5]
5	8 vs 9	8 (left)	[1, 2, 5, 5, 8]
6	left side empty	copy the rest: 9	[1, 2, 5, 5, 8, 9]

Compare the two front elements, copy the smaller one to tmp, advance that side; when one side is exhausted, copy the rest of the other side without further comparisons. Merging halves of total length m costs at most m − 1 comparisons and exactly m copies (here 5 comparisons, 6 copies).

The whole sort, step by step, on [6, 3, 8, 1, 5, 4, 7, 2]. First the splits (no work is done here, just index arithmetic):

                 [6 3 8 1 5 4 7 2]
                /                 \
         [6 3 8 1]               [5 4 7 2]
         /       \               /       \
      [6 3]     [8 1]         [5 4]     [7 2]
      /  \      /  \          /  \      /  \
    [6]  [3]  [8]  [1]      [5]  [4]  [7]  [2]      <- 1 element: sorted

Then the merges, in the order the recursion does them:

#	merge	result	whole array afterwards
1	[6] + [3]	[3, 6]	[3, 6, 8, 1, 5, 4, 7, 2]
2	[8] + [1]	[1, 8]	[3, 6, 1, 8, 5, 4, 7, 2]
3	[3, 6] + [1, 8]	[1, 3, 6, 8]	[1, 3, 6, 8, 5, 4, 7, 2]
4	[5] + [4]	[4, 5]	[1, 3, 6, 8, 4, 5, 7, 2]
5	[7] + [2]	[2, 7]	[1, 3, 6, 8, 4, 5, 2, 7]
6	[4, 5] + [2, 7]	[2, 4, 5, 7]	[1, 3, 6, 8, 2, 4, 5, 7]
7	[1, 3, 6, 8] + [2, 4, 5, 7]	[1, 2, 3, 4, 5, 6, 7, 8]	[1, 2, 3, 4, 5, 6, 7, 8]

Notice that the recursion finishes the whole left half (merges 1–3) before it touches the right half. There are 3 levels of merging for 8 = 2³ elements, and each level moves all 8 elements once: 3 × 8 work. In general: log₂ n levels × n work = n log₂ n.

Properties:

• Time Θ(n log n) in every case. There are about log₂ n levels of recursion and each level merges n elements in total. Merge sort does not benefit from sorted input (unlike insertion sort), but it never degrades either.
• Extra space O(n) for tmp (plus O(log n) stack). Merge sort is not in place; that is its main cost.
• Stable, because on a tie a[i] <= a[j] takes the element from the left half, which came first in the original array. Write < and the sort still sorts, but equal keys from the right half jump ahead: the sort is no longer stable.

Quick sort

Quick sort also divides and conquers, but does the work before recursing: partition the array around a pivot so that everything ≤ pivot is on its left and everything greater is on its right. The pivot is then in its final position, and the two sides are sorted recursively. No merge step is needed.

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

private static void quickSort(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(a, lo, hi);     // a[p] is now in its final place
    quickSort(a, lo, p - 1);
    quickSort(a, p + 1, hi);
}

// Lomuto partition: pivot = a[hi]. Invariant: a[lo..i] <= pivot < a[i+1..j-1]
private static int partition(int[] a, int lo, int hi) {
    int pivot = a[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; j++) {
        if (a[j] <= pivot) {
            i++;
            swap(a, i, j);
        }
    }
    swap(a, i + 1, hi);               // put the pivot between the two regions
    return i + 1;
}

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

The Lomuto partition keeps a[lo..i] ≤ pivot and a[i+1..j-1] > pivot while j scans. Picture the array as four zones:

  lo        i  i+1       j-1  j          hi
  [  <= pivot ][   > pivot   ][ not seen ][pivot]

j walks right through the "not seen" zone. A big element simply stays where it is (the "> pivot" zone grows). A small element is swapped to the end of the "<= pivot" zone (i moves one step first). Trace partition on [6, 3, 8, 1, 5, 4] (pivot 4, i starts at −1):

j	a[j]	action	array afterwards
0	6	6 > 4, nothing	[6, 3, 8, 1, 5, 4]
1	3	i = 0, swap a[0], a[1]	[3, 6, 8, 1, 5, 4]
2	8	nothing	[3, 6, 8, 1, 5, 4]
3	1	i = 1, swap a[1], a[3]	[3, 1, 8, 6, 5, 4]
4	5	nothing	[3, 1, 8, 6, 5, 4]
end		swap a[2], a[5]	[3, 1, 4, 6, 5, 8]

partition returns 2: the 4 is final, and quickSort recurses on [3, 1] and [6, 5, 8]. Partitioning m elements makes exactly m − 1 comparisons.

The whole sort, continuing the same example. Each row is one call of partition:

call	range before	pivot	range after	pivot ends at	whole array afterwards
1	a[0..5] = [6, 3, 8, 1, 5, 4]	4	[3, 1, 4, 6, 5, 8]	2	[3, 1, 4, 6, 5, 8]
2	a[0..1] = [3, 1]	1	[1, 3]	0	[1, 3, 4, 6, 5, 8]
3	a[3..5] = [6, 5, 8]	8	[6, 5, 8]	5	[1, 3, 4, 6, 5, 8]
4	a[3..4] = [6, 5]	5	[5, 6]	3	[1, 3, 4, 5, 6, 8]

Ranges of size 0 or 1 (like [3] after call 2 or [6] after call 4) return at once. The array is sorted: [1, 3, 4, 5, 6, 8].

Cost depends on the pivot.

• Best/average case: the pivot lands near the middle, the recursion is about log₂ n deep, and each level does O(n) work: O(n log n). On random input the average is about 1.39 n log₂ n comparisons, and the tight inner loop makes quick sort the fastest general-purpose sort in practice.
• Worst case: the pivot is always the smallest or largest element. One side is empty, the other has m − 1 elements, so the work is (n−1) + (n−2) + … + 1 = n(n−1)/2: O(n²). With a first- or last-element pivot this happens on already sorted or reverse-sorted input — exactly the input people most often sort "just in case". An array of equal keys hits the same worst case with Lomuto, since every element satisfies a[j] <= pivot.

See the worst case happen on the sorted array [1, 2, 3, 4, 5] with the last element as pivot:

partition [1 2 3 4 5]  pivot 5 -> left side [1 2 3 4], right side empty   (4 comparisons)
partition [1 2 3 4]    pivot 4 -> left side [1 2 3],   right side empty   (3 comparisons)
partition [1 2 3]      pivot 3 -> left side [1 2],     right side empty   (2 comparisons)
partition [1 2]        pivot 2 -> left side [1],       right side empty   (1 comparison)
total 4 + 3 + 2 + 1 = 10 = n(n-1)/2

Each call removes only the pivot, so the recursion is n − 1 levels deep instead of log₂ n.

Choosing the pivot. Pick a random index, or the median of three (first, middle, last), and swap it into a[hi] before partitioning. Both make the quadratic case vanishingly unlikely on real data; neither changes the worst case in theory. In the student analogy: never ask "the last student in the line" to be the pivot when the line is already ordered by height.

Space. Quick sort is in place: it only swaps within the array. The recursion stack is O(log n) deep on average but O(n) in the worst case; recursing into the smaller side first and looping on the larger one caps it at O(log n).

Stability. Quick sort is not stable: a swap can carry an element over an equal one lying between the two positions.

Heap sort, in outline

A binary max-heap (Chapter 11) is an array in which every element is ≥ its two "children" at indices 2i+1 and 2i+2, so the maximum is at index 0. Heap sort:

1. rearranges the array into a max-heap in O(n) time (heapify);
2. repeats n − 1 times: swap a[0] (the maximum) with the last element of the heap, shrink the heap by one, and sift down the new root to restore the heap — O(log n) each.

A short run on [4, 10, 3, 5, 1] (the part after | is already sorted; Chapter 11 shows every sift step):

after heapify   [10, 5, 3, 4, 1 |              ]
pass 1          [ 5, 4, 3, 1    | 10           ]   10 swapped to the back
pass 2          [ 4, 1, 3       |  5, 10       ]
pass 3          [ 3, 1          |  4,  5, 10   ]
pass 4          [ 1             |  3,  4,  5, 10]

So heap sort is O(n log n) in the worst case and in place (O(1) extra space) — the only common sort with both guarantees. It is not stable, and its jumps around the array make poor use of the cache, so in practice it is slower than quick sort. Library sorts use it as a safety net: introsort switches from quick sort to heap sort when the recursion gets too deep. You will implement heaps in Chapter 11.

Counting sort

If the keys are small integers in 0..k, you do not need to compare them at all: count how many times each value occurs, turn the counts into positions, and place each element directly.

// Stable counting sort for values in 0..k
static int[] countingSort(int[] a, int k) {
    int[] count = new int[k + 1];
    for (int x : a) count[x]++;                    // 1. histogram
    for (int v = 1; v <= k; v++) count[v] += count[v - 1];  // 2. prefix sums
    int[] out = new int[a.length];
    for (int i = a.length - 1; i >= 0; i--) {      // 3. right to left keeps it stable
        out[--count[a[i]]] = a[i];
    }
    return out;
}

Worked example: a = [3, 1, 4, 1, 0, 3, 2], k = 4.

value v            0  1  2  3  4
1. count[v]        1  2  1  2  1     (how many of each value)
2. prefix sums     1  3  4  6  7     (how many values are <= v)

Step 3 walks a from right to left. For each element, decrease its counter first, then use the counter as the index:

i	a[i]	count[a[i]] becomes	goes to	out afterwards
6	2	3	out[3]	[_, _, _, 2, _, _, _]
5	3	5	out[5]	[_, _, _, 2, _, 3, _]
4	0	0	out[0]	[0, _, _, 2, _, 3, _]
3	1	2	out[2]	[0, _, 1, 2, _, 3, _]
2	4	6	out[6]	[0, _, 1, 2, _, 3, 4]
1	1	1	out[1]	[0, 1, 1, 2, _, 3, 4]
0	3	4	out[4]	[0, 1, 1, 2, 3, 3, 4]

The last 1 of the input (index 3) went to out[2], the later of the two slots, and the first 1 (index 1) went to out[1]. The two 1s kept their order: that is stability.

After step 2, count[v] is the number of elements ≤ v, which is one past the last slot that value v will occupy. Filling from right to left with --count[v] places equal keys in their original order, so the sort is stable (it matters when the "keys" are fields of larger records).

Cost: O(n + k) time and O(n + k) extra space. Brilliant when k = O(n) (exam marks 0–100, ages, days of the month); useless when k is huge — sorting 1 000 values in the range 0..10⁹ would need a count array of a billion ints.

Radix sort (LSD)

Least-significant-digit radix sort sorts integers digit by digit, starting with the units, using a stable counting sort on each digit (base b = 10 here, so each pass counts digits 0–9):

// LSD radix sort for non-negative ints, base 10
static void radixSort(int[] a) {
    int max = 0;
    for (int x : a) max = Math.max(max, x);
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingPassOnDigit(a, exp);               // a stable pass on one digit
    }
}

static void countingPassOnDigit(int[] a, int exp) {
    int[] count = new int[10];
    for (int x : a) count[(x / exp) % 10]++;
    for (int d = 1; d < 10; d++) count[d] += count[d - 1];
    int[] out = new int[a.length];
    for (int i = a.length - 1; i >= 0; i--) {
        out[--count[(a[i] / exp) % 10]] = a[i];
    }
    System.arraycopy(out, 0, a, 0, a.length);
}

The expression (x / exp) % 10 extracts one digit: with x = 853, exp = 1 gives 3, exp = 10 gives 5, exp = 100 gives 8.

Trace on [53, 21, 38, 11, 43]:

pass	sorted by	result
1	units digit	[21, 11, 53, 43, 38]
2	tens digit	[11, 21, 38, 43, 53]

In pass 1, 53 and 43 tie on the units digit (3), so they keep their input order 53, 43; pass 2 then orders them by the tens digit. Numbers that tie in pass 2 keep the order pass 1 gave them. The invariant is: after pass p, the array is sorted by the last p digits. It only holds because every pass is stable — a tie on the current digit must keep the order established by the lower digits.

A bigger example with three passes, [170, 45, 75, 90, 802, 24, 2, 66] (a short number has leading zeros: 45 is 045, 2 is 002):

pass	digit used	result
1	units	[170, 90, 802, 2, 24, 45, 75, 66]
2	tens	[802, 2, 24, 45, 66, 170, 75, 90]
3	hundreds	[2, 24, 45, 66, 75, 90, 170, 802]

After pass 2, look at 802 and 2: both have tens digit 0, and 802 stays before 2 because it was before 2 after pass 1. Pass 3 then separates them by the hundreds digit (8 vs 0).

Cost: d passes of O(n + b), so O(d(n + b)) for d-digit keys in base b. For 32-bit ints processed one byte at a time (b = 256, d = 4) that is linear in n. Radix sort needs keys that break into digits (integers, fixed-length strings); negative numbers need extra handling.

Bucket sort

Bucket sort suits real keys spread uniformly over a known range, say [0, 1). Create n buckets (lists), put x into bucket (int) (x * n), sort each bucket with insertion sort, then concatenate the buckets in order. With uniform input each bucket holds O(1) elements on average, so the expected time is O(n). If the data are skewed and most keys fall into one bucket, you are back to insertion sort on almost everything: O(n²) worst case.

For example, with n = 5 and keys [0.42, 0.07, 0.91, 0.45, 0.63]: 0.07 → bucket 0, 0.42 and 0.45 → bucket 2, 0.63 → bucket 3, 0.91 → bucket 4. Only bucket 2 needs any sorting, and it holds two elements.

Stability and in-place: the summary

A sort is stable if elements with equal keys keep their relative order. That matters when you sort records by one field after another: sort students by name, then stably by grade, and each grade group stays in name order.

Example: the list is already in name order: Ana (B), Bo (A), Cy (B), Di (A). A stable sort by grade gives

Bo (A), Di (A), Ana (B), Cy (B)     <- inside each grade, still in name order

An unstable sort may give Di (A), Bo (A), Cy (B), Ana (B): sorted by grade, but the name order is lost.

A sort is in place if it uses only O(1) extra memory besides the array (recursion stack aside).

Algorithm	Best	Average	Worst	Extra space	Stable?	In place?
Insertion	O(n)	O(n²)	O(n²)	O(1)	Yes	Yes
Merge	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes	No
Quick (Lomuto)	O(n log n)	O(n log n)	O(n²)	O(log n) stack avg	No	Yes
Heap	O(n log n)	O(n log n)	O(n log n)	O(1)	No	Yes
Counting	O(n + k)	O(n + k)	O(n + k)	O(n + k)	Yes	No
Radix (LSD)	O(d(n + b))	O(d(n + b))	O(d(n + b))	O(n + b)	Yes	No
Bucket	O(n)	O(n)	O(n²)	O(n)	Yes*	No

* if the per-bucket sort is stable.

The Ω(n log n) lower bound for comparison sorts

Merge, quick, heap and insertion sort learn about the input only by comparing two elements. Any such algorithm, run on inputs of size n, can be drawn as a decision tree: each internal node is a comparison a[i] <= a[j]?, the two branches are the two outcomes, and each leaf is the final arrangement the algorithm outputs.

Here is a decision tree that sorts three elements a, b, c:

                        a <= b ?
                  yes /          \ no
               b <= c ?            a <= c ?
            yes /    \ no       yes /    \ no
          a b c    a <= c ?     b a c    b <= c ?
                 yes /  \ no           yes /  \ no
                a c b   c a b         b c a   c b a

It has 3! = 6 leaves (one for each possible order) and height 3: in the worst case the algorithm asks 3 questions.

1. The algorithm must be able to produce every one of the n! orderings of distinct keys, so the tree has at least n! leaves.
2. A binary tree of height h has at most 2ʰ leaves, so 2ʰ ≥ n!, i.e. h ≥ log₂(n!).
3. The height is the number of comparisons on the worst input, and log₂(n!) ≥ log₂((n/2)^(n/2)) = (n/2) log₂(n/2), which is Ω(n log n).

So no comparison sort can beat n log n in the worst case; merge sort and heap sort are optimal up to a constant factor. Small example: 3 elements have 3! = 6 orderings, so at least ⌈log₂ 6⌉ = 3 comparisons are needed in the worst case. For 5 elements, 5! = 120 and ⌈log₂ 120⌉ = 7.

Counting, radix and bucket sort escape the bound because they do not only compare: they use key values as array indices. The price is an assumption about the keys (small range, fixed number of digits, uniform distribution).

What Java actually uses

• Arrays.sort(int[]), Arrays.sort(double[]) and the other primitive overloads use a tuned dual-pivot quick sort (two pivots, three partitions), with insertion sort for tiny ranges. It is in place and not stable — but for primitives stability is invisible: two equal ints are indistinguishable.
• Arrays.sort(Object[]), Arrays.sort(T[], Comparator), Collections.sort and List.sort use TimSort, a merge-sort/insertion-sort hybrid that finds existing sorted runs and merges them. It is stable, O(n log n) in the worst case, O(n) on already sorted input, and needs up to n/2 extra references.
• There is no Arrays.sort(int[], Comparator): a Comparator needs objects. To sort ints in descending order, box them (Integer[]) or sort ascending and reverse.

Why the difference? Objects can be equal by compareTo yet be different records, so users rely on stability (sort by name, then by grade). Primitives do not need it, so Java uses the faster quick sort, which needs no extra array.

Choosing an algorithm

• Just sorting in Java? Use Arrays.sort / List.sort. You will not beat them.
• Small or nearly sorted data: insertion sort.
• Need stability or a guaranteed O(n log n): merge sort (TimSort). Also the choice for linked lists and for data too large for memory (external merge sort).
• Fastest average for primitives in memory, no stability needed: quick sort with a good pivot.
• Guaranteed O(n log n) with O(1) extra memory: heap sort.
• Integer keys in a small range: counting sort; fixed-width integer or string keys: radix sort; uniform real keys: bucket sort.

Key takeaways

• Insertion sort costs O(n + inversions): O(n) on sorted data, O(n²) on reversed data. Libraries use it for tiny or nearly-sorted ranges.
• Merge sort: split in half, sort halves, merge. Always Θ(n log n), stable (ties go left), but needs O(n) extra space.
• Quick sort: partition around a pivot, then recurse. O(n log n) on average and fastest in practice, but O(n²) when the pivot is always the smallest or largest (sorted input with a last-element pivot). Not stable, in place.
• Heap sort: always O(n log n) and in place, but not stable and slower in practice.
• Counting, radix and bucket sort do not compare keys; they beat n log n only under assumptions (small range, fixed digits, uniform values). LSD radix sort needs a stable pass for each digit.
• Stable = equal keys keep their order; in place = O(1) extra memory. These are separate properties.
• Any comparison sort needs Ω(n log n) comparisons in the worst case, because a decision tree with n! leaves has height at least log₂(n!).
• Java: dual-pivot quick sort for primitive arrays, stable TimSort for objects.