Merge sort

The three sorts from the last lesson all do about n² work. At n = 10⁵ that is 10 billion steps, far over the budget. Merge sort does the same job in under 2 million comparisons.

The idea is short. The part that confuses most learners is the recursion: how can you "sort each half" when nothing is sorted yet? The answer is the base case, and this lesson draws it.

Read the problem

It is the same problem as in the last lesson. Only the limit changed, and the limit decides the approach:

The questions to ask are the same as in the last lesson: repeated values, negative values, one item. One new question matters here: may you use extra memory? Merge sort needs a second array.

The slow way

Any sort from the last lesson works, but it is too slow. A run of insertion sort on 100,000 random numbers made about 2.5 billion comparisons and took about 3 seconds in Node.js.

The waste: every item gets compared with almost every other item, one at a time.

The key insight: merging sorted piles is cheap

Picture two piles of exam papers, each already sorted by roll number. To make one sorted pile:

1. Look at the top paper of each pile.
2. Take the smaller one and put it on the new pile.
3. Repeat until both piles are empty.

Each paper is touched once. Two sorted piles of total size n merge in about n steps, not n².

Here is that merge on our example, with both halves already sorted. i reads the left half and j reads the right half:

So if the two halves were sorted, one cheap merge would finish the job. How do you sort each half? The same way: split it and merge it.

Keep splitting until each piece has one item. One item is always sorted. That is the base case.

Divide and conquer

This plan has a name: divide and conquer. Merge sort does it in two moves.

Split on the way down

┌────────────────────────────────────────────┐
│                                            │
│              [13,46,24,52,20,9]            │
│             ┌─────────┴─────────┐          │
│         [13,46,24]          [52,20,9]      │
│         ┌───┴───┐           ┌───┴───┐      │
│      [13,46]   [24]      [52,20]   [9]     │
│      ┌──┴──┐             ┌──┴──┐           │
│    [13]   [46]         [52]   [20]         │
│                                            │
└────────────────────────────────────────────┘

Merge on the way back up

┌────────────────────────────────────────────┐
│                                            │
│    [13]   [46]         [52]   [20]         │
│      └──┬──┘             └──┬──┘           │
│      [13,46]   [24]      [20,52]   [9]     │
│         └───┬───┘           └───┬───┘      │
│         [13,24,46]          [9,20,52]      │
│             └─────────┬─────────┘          │
│              [9,13,20,24,46,52]            │
│                                            │
└────────────────────────────────────────────┘

All the real work happens in the merges, after the recursive calls return. On our six numbers, the five merges made 10 comparisons in total.

The code

The split does not copy the array. It works on index ranges: low and high mark the piece this call sorts.

JavaPythonTypeScript

void mergeSort(int[] a, int low, int high) {
    if (low >= high) return;
    int mid = (low + high) / 2;
    mergeSort(a, low, mid);
    mergeSort(a, mid + 1, high);
    merge(a, low, mid, high);
}

• Base case: low >= high means the piece has one item (or none). It is sorted.
• mid splits the piece. The left half is low..mid, the right half is mid + 1..high.
• The two calls sort each half. Then merge combines them.
• The first call: TypeScript fills in low and high by default. Java and Python have no default that can read the array, so call mergeSort(a, 0, a.length - 1) or merge_sort(a, 0, len(a) - 1).
• Integer division: Java's / drops the fraction on int values. Python needs //, and TypeScript needs Math.floor.

JavaPythonTypeScript

void merge(int[] a, int low, int mid, int high) {
    int[] temp = new int[high - low + 1];
    int i = low, j = mid + 1, k = 0;
    while (i <= mid && j <= high) {
        if (a[i] <= a[j]) temp[k++] = a[i++];
        else temp[k++] = a[j++];
    }
    while (i <= mid) temp[k++] = a[i++];
    while (j <= high) temp[k++] = a[j++];
    for (k = 0; k < temp.length; k++) a[low + k] = temp[k];
}

• temp collects the merged piece. Java sizes it once, high - low + 1 slots, and fills it with k.
• i is the next unread item of the left half, j of the right half.
• The first loop copies the smaller front value. The <= takes the left one on a tie, so equal values keep their order. That makes merge sort stable.
• The two short loops copy whatever is left. Only one of them does any work. Python copies each leftover part in one extend call.
• The last step writes temp back over a[low..high]. Python does it with one slice assignment.

Common mistakes

• < instead of <= in the merge. The output is still sorted, but equal values can swap order. The sort is no longer stable.
• Splitting into low..mid and mid..high. For a piece of two items, the right call gets the same piece again, and the recursion never ends.
• Passing the length as high. high is the last index, so the first call passes the length minus 1.
• Dropping the leftover copies. The values left in one half never reach temp.

Why it is O(n log n)

┌────────────────────────────────────────────────┐
│                                                │
│   pieces   items              merge work       │
│                                                │
│   8 × 1    █ █ █ █ █ █ █ █                     │
│                               8 moves          │
│   4 × 2    ██ ██ ██ ██                         │
│                               8 moves          │
│   2 × 4    ████ ████                           │
│                               8 moves          │
│   1 × 8    ████████                            │
│                                                │
│   █ = one item. 4 × 2 = 4 pieces of 2 items.   │
│   3 levels (log of 8) × 8 moves = 24           │
│   in general: log n levels × n = n log n       │
│                                                │
└────────────────────────────────────────────────┘

Count it out loud:

• Work per level: the merges on one level touch every item once. That is n.
• Number of levels: each split halves the pieces. You can halve n about log n times before you reach 1. For n = 10⁵, that is 17.
• Total: n × log n. For 10⁵ items, about 1.7 million steps.

The split does not depend on the data. So sorted, reversed and random arrays all cost O(n log n). There is no bad input.

Space. temp holds up to n items, and the call stack holds about log n frames. Extra space is O(n). This is the price merge sort pays.

Side by side

Measured on the same 100,000 random numbers in Node.js:

How to spot merge sort

The last one has its own lesson later: "Count inversions with merge sort". The merge step sees exactly which left items are bigger than a right item.

The template to remember: base case, split at mid, sort left, sort right, merge.

take U forwardYouTube

Read more

• Overview of merge sort on Khan Academy, divide and conquer with pictures
• Getting things sorted in V8, why V8 moved to TimSort and how it merges runs
• VisuAlgo: sorting, pick merge sort and watch the merges
• Merge sort on Wikipedia, with the bottom-up version and linked lists

Next: quick sort, which skips the extra array by splitting around a pivot instead.