Merge sort

Introduction

Divide and conquer solves a problem by splitting it into smaller problems of the same kind, solving those (usually by recursion), and combining the answers. Merge sort is the classic example, and it sorts in O(n log n) time, whatever the input.

Merge sort is the first algorithm in this course that beats O(n²). It rests on one simple observation: joining two sorted lists is far easier than sorting a jumbled one.

How it works

Merging two sorted arrays

#include <stdio.h>

int main(void) {
    int a[] = {2, 5, 9};
    int b[] = {1, 6, 7, 10};
    int out[7];
    int i = 0, j = 0, k = 0;
    while (i < 3 && j < 4) {
        if (a[i] <= b[j]) out[k++] = a[i++];
        else out[k++] = b[j++];
    }
    while (i < 3) out[k++] = a[i++];
    while (j < 4) out[k++] = b[j++];
    for (k = 0; k < 7; k++) printf("%d ", out[k]);
    printf("\n");
    return 0;
}

The key step is merging: two sorted arrays become one sorted array in a single pass. Look at the front of each; copy the smaller one to the output and move past it. When one array runs out, copy the rest of the other. Every item is copied once, so merging n items is O(n).

Why O(n log n)?

Halving n items reaches single items after log₂ n levels. At each level the merges together copy all n items once. So the total is n × log₂ n.

Merge sort is stable (<= takes from the left half on a tie) and its time is always O(n log n), but it needs an extra array of n items for merging. It is also the natural way to sort a linked list, and to sort data too big for memory.

Syntax

void merge_sort(int a[], int lo, int hi) {
    if (lo >= hi) return;          // the base case
    int mid = (lo + hi) / 2;
    merge_sort(a, lo, mid);        // conquer the left half
    merge_sort(a, mid + 1, hi);    // conquer the right half
    merge(a, lo, mid, hi);         // combine
}

Example

#include <stdio.h>

void merge(int a[], int lo, int mid, int hi) {
    int tmp[8];
    int i = lo, j = mid + 1, k = 0;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi) tmp[k++] = a[j++];
    for (k = 0; k < hi - lo + 1; k++) a[lo + k] = tmp[k];
}

void merge_sort(int a[], int lo, int hi) {
    if (lo >= hi) return;   // 0 or 1 item: already sorted
    int mid = (lo + hi) / 2;
    merge_sort(a, lo, mid);
    merge_sort(a, mid + 1, hi);
    merge(a, lo, mid, hi);
}

int main(void) {
    int a[] = {38, 27, 43, 3, 9, 82};
    merge_sort(a, 0, 5);
    for (int i = 0; i < 6; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

1. Divide: split a[lo .. hi] at mid.
2. Conquer: sort each half with a recursive call. A range of 0 or 1 items is already sorted: that is the base case.
3. Combine: merge the two sorted halves.

Watch the call stack: the calls go down to single items, and the merges happen on the way back up.

[38 27 43 3 9 82]
[38 27 43]      [3 9 82]
[38 27] [43]    [3 9] [82]
[38] [27]       [3] [9]
-- merge back up --
[27 38] [43]    [3 9] [82]
[27 38 43]      [3 9 82]
[3 9 27 38 43 82]

Line by line

1. merge copies from two sorted runs, a[lo .. mid] and a[mid + 1 .. hi], into tmp.
2. i and j point at the front of each run, and k is the next free cell of tmp.
3. The first while loop always copies the smaller front item. <= takes from the left on a tie, which keeps the sort stable.
4. The next two while loops copy whatever is left. Only one of them does anything.
5. The for loop copies the merged items back into a, starting at lo.
6. merge_sort stops when the range has 0 or 1 items. Otherwise it sorts each half and merges them.
7. main sorts the six numbers from index 0 to 5, and prints them in order.

Expected result

3 9 27 38 43 82 

In the real world

Sorting a file too large for memory is done with merge sort's idea: sort pieces that fit, write them out, and merge the pieces. The same merge step is how databases join sorted data and how Timsort combines its runs.

Common mistakes

• Using < instead of <= in the merge: still sorted, but no longer stable.
• Forgetting to copy the leftovers of one half after the other runs out.
• Splitting as lo .. mid - 1 and mid .. hi with mid = (lo + hi) / 2: for two items, one half is empty and the other never shrinks.

Best practices

• Make the merge work alone, with its own tests, before adding recursion.
• Allocate one temporary array and pass it around in real code, rather than making a new one per call.
• Test with one item, with two items, and with duplicates.

Summary

Merge sort splits an array in half, sorts each half and merges them in O(n). With log₂ n levels that is O(n log n) for every input, at the cost of an extra array, and the sort is stable.

Mark lesson complete