Lesson 14.2 · Sorting and Divide & Conquer

Merge Sort

Split in half, sort each half recursively, merge the two sorted halves with two pointers. Always O(n log n), stable, O(n) extra space.

15 min

Think of it like this

Two teachers each sort half the exam papers alphabetically. To combine them, you look at the top paper of each pile and take whichever name comes first, again and again, until both piles are empty.

1.Divide, conquer, combine

The recursion splits until pieces have one element (already sorted). The merge step walks two sorted halves with two pointers, always taking the smaller front element: O(n) per level. There are log n levels, so O(n log n) total, whatever the input.

MergeSort.java

import java.util.Arrays;

public class Main {
    static void sort(int[] a, int[] tmp, int lo, int hi) {      // sorts a[lo..hi]
        if (lo >= hi) return;
        int mid = (lo + hi) >>> 1;
        sort(a, tmp, lo, mid);
        sort(a, tmp, mid + 1, hi);
        int i = lo, j = mid + 1, k = lo;
        while (i <= mid && j <= hi) tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];   // <= keeps it stable
        while (i <= mid) tmp[k++] = a[i++];
        while (j <= hi) tmp[k++] = a[j++];
        System.arraycopy(tmp, lo, a, lo, hi - lo + 1);
    }
    public static void main(String[] args) {
        int[] a = {5, 2, 8, 1, 9, 6, 2};
        sort(a, new int[a.length], 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }
}

Output

[1, 2, 2, 5, 6, 8, 9]

▶ Dry run: Merging two sorted halvesleft = [2, 5, 8], right = [1, 6, 9]

↑i

↑j

merged(list)

empty

Step 1/4Compare the fronts: 2 vs 1. Take 1.

Remember

Guaranteed O(n log n), stable.
O(n) extra space for merging.
The merge step is reusable (merging lists, counting inversions).

Common mistakes

Using < in the merge (breaks stability).
Allocating a new temp array in every call (slow).

Command Palette

Merge Sort

1.Divide, conquer, combine