jario_
Back to overview

Algorithms and Data Structures · Chapter 3

Fast sorting algorithms

Bubble, Selection and Insertion Sort need O(n²) steps. With 1,000 elements that is about a million comparisons, with a million elements already a trillion. The algorithms in this chapter do the same in O(n log n), so with a million elements in about 20 million steps. The trick behind them is called divide and conquer.

Divide and conquer: Merge Sort

Divide and conquer splits a problem into smaller subproblems of the same kind, solves them recursively and puts the solutions together. Merge Sort does it like this:

  1. Base case: An array with 0 or 1 element is already sorted.
  2. Divide: Split the array in the middle (length / 2) into two halves.
  3. Conquer: Sort both halves recursively.
  4. Combine: Merge the two sorted halves.

When merging, two pointers point to the start of both halves. The smaller element moves into the result, and only its pointer moves on. Once one half is empty, the rest of the other one is appended.

Running time: The array is halved log₂ n times, and on each level every element is merged once in total. That gives O(n log n), always, even in the worst case. The price: Merge Sort needs O(n) extra memory for the helper arrays.

import java.util.Arrays;
public class Main {    public static int[] mergeSort(int[] values) {        if (values.length <= 1) {            return values;        }        int mid = values.length / 2;        int[] left = mergeSort(Arrays.copyOfRange(values, 0, mid));        int[] right = mergeSort(Arrays.copyOfRange(values, mid, values.length));        return merge(left, right);    }
    public static int[] merge(int[] a, int[] b) {        int[] result = new int[a.length + b.length];        int i = 0;        int j = 0;        int k = 0;        while (i < a.length && j < b.length) {            if (a[i] <= b[j]) {                result[k++] = a[i++];            } else {                result[k++] = b[j++];            }        }        while (i < a.length) {            result[k++] = a[i++];        }        while (j < b.length) {            result[k++] = b[j++];        }        return result;    }
    public static void main(String[] args) {        int[] values = {38, 27, 43, 3, 9, 82, 10};        System.out.println(Arrays.toString(mergeSort(values)));        System.out.println(Arrays.toString(merge(new int[]{1, 4, 9}, new int[]{2, 3, 10})));    }}

Quicksort

Quicksort divides differently: it picks a pivot element and partitions the array so that everything smaller is to its left and everything else to its right. Afterwards the pivot is at its final place p. Only the ranges left and right of it are sorted recursively. No combining step is needed, and Quicksort works in place, without a helper array.

In Lomuto's partition, the pivot is the last element a[high]. An index i marks where the next smaller element goes. A second index j runs from low to high - 1. If a[j] < pivot, a[i] and a[j] are swapped and i moves on. At the end the pivot swaps with a[i].

Running time: If the pivot splits the range roughly in the middle, you get O(n log n) as with Merge Sort, and that is the average. But if the pivot is always the smallest or largest element, the range only shrinks by one: O(n²) in the worst case. With Lomuto, this happens precisely for an already sorted array. In practice the pivot is therefore often chosen at random or as the median of three elements.

import java.util.Arrays;
public class Main {    public static void quickSort(int[] a, int low, int high) {        if (low >= high) {            return;        }        int p = partition(a, low, high);        quickSort(a, low, p - 1);        quickSort(a, p + 1, high);    }
    // Lomuto: the last element is the pivot    public static int partition(int[] a, int low, int high) {        int pivot = a[high];        int i = low;        for (int j = low; j < high; j++) {            if (a[j] < pivot) {                swap(a, i, j);                i++;            }        }        swap(a, i, high);        return i;    }
    public static void swap(int[] a, int i, int j) {        int tmp = a[i];        a[i] = a[j];        a[j] = tmp;    }
    public static void main(String[] args) {        int[] a = {7, 2, 9, 4, 5};        int p = partition(a, 0, a.length - 1);        System.out.println("pivot at " + p + ": " + Arrays.toString(a));
        int[] b = {38, 27, 43, 3, 9, 82, 10};        quickSort(b, 0, b.length - 1);        System.out.println(Arrays.toString(b));    }}

Counting Sort

A comparison-based algorithm can never be faster than O(n log n). Counting Sort gets around this limit because it does not compare at all. But it only works for small, non-negative whole numbers, such as dice rolls, grades or points:

  1. Create a count array count of length max + 1.
  2. For each value v: count[v]++.
  3. Run over count and write each value v exactly count[v] times into the result.

Running time: O(n + k), where k is the number of possible values. For 100 dice rolls with 6 possible faces, that is unbeatable. For values up to a billion, though, the count array would need a billion slots.

import java.util.Arrays;
public class Main {    public static int[] countingSort(int[] values, int max) {        int[] count = new int[max + 1];        for (int v : values) {            count[v]++;        }        int[] result = new int[values.length];        int k = 0;        for (int v = 0; v <= max; v++) {            for (int c = 0; c < count[v]; c++) {                result[k++] = v;            }        }        return result;    }
    public static void main(String[] args) {        int[] dice = {6, 1, 3, 6, 2, 1, 5, 6};        System.out.println(Arrays.toString(countingSort(dice, 6)));    }}

Stability and comparison

A sorting algorithm is stable if elements with equal keys stay in their original order. That matters when you sort by several criteria: first alphabetically, then stably by grade, and for equal grades the alphabetical order is kept.

Merge Sort is stable if merge takes the element from the left half on a tie, so it compares with <=. With <, stability is lost. Quicksort is not stable, because the swaps move equal elements far apart.

  • Merge Sort: always O(n log n), O(n) extra memory, stable.
  • Quicksort: O(n log n) on average, O(n²) in the worst case, in place, not stable.
  • Counting Sort: O(n + k), O(k) extra memory for the counters, only for small whole numbers.

Java uses both: Arrays.sort for int[] is a descendant of Quicksort, for objects and List.sort it is a stable algorithm related to Merge Sort.

import java.util.ArrayList;import java.util.List;
public class Main {    record Order(String id, int priority) {}
    public static List<Order> sortByPriority(List<Order> orders) {        if (orders.size() <= 1) {            return new ArrayList<>(orders);        }        int mid = orders.size() / 2;        List<Order> left = sortByPriority(orders.subList(0, mid));        List<Order> right = sortByPriority(orders.subList(mid, orders.size()));        List<Order> result = new ArrayList<>();        int i = 0;        int j = 0;        while (i < left.size() && j < right.size()) {            // <= keeps equal keys in their order: stable            if (left.get(i).priority() <= right.get(j).priority()) {                result.add(left.get(i++));            } else {                result.add(right.get(j++));            }        }        while (i < left.size()) {            result.add(left.get(i++));        }        while (j < right.size()) {            result.add(right.get(j++));        }        return result;    }
    public static void main(String[] args) {        List<Order> orders = List.of(            new Order("A", 2), new Order("B", 1), new Order("C", 2),            new Order("D", 1), new Order("E", 2));        for (Order o : sortByPriority(orders)) {            System.out.println(o.priority() + " " + o.id());        }    }}

Common mistakes

  • Forgetting the rest when merging

    The main loop of merge ends as soon as one half is empty. If the loops that copy the rest of the other half are missing, zeros remain at the end of the result. You need both: one for the rest on the left and one for the rest on the right.

  • Wrong bounds in the recursion

    In Quicksort, the pivot at index p no longer belongs to either part. If you recurse with quickSort(a, low, p) instead of p - 1, the same range can come up again and again until a StackOverflowError follows. The same happens in Merge Sort with bounds in the same array (left..mid, mid+1..right) if mid appears twice or not at all.

  • Losing stability with <

    In merge, if (a[i] < b[j]) looks harmless. On a tie, however, it takes the element from the right half first, even though it originally came later. The result is still sorted, but no longer stable. The correct comparison is <=.