Step 2 of 6

Merge sort

Merge sort is the classic divide and conquer algorithm:

1. Divide: split the array into two halves.
2. Conquer: sort each half, recursively. An array of 0 or 1 elements is already sorted: that's the base case.
3. Combine: merge the two sorted halves into one sorted array.

The merge is the heart of it. With two sorted lists, the smallest remaining element is always at the front of one of them, so you repeatedly take the smaller front:

#include <iostream>
#include <vector>

std::vector<int> merge(const std::vector<int>& a, const std::vector<int>& b) {
    std::vector<int> out;
    out.reserve(a.size() + b.size());
    std::size_t i = 0, j = 0;
    while (i < a.size() && j < b.size()) {
        if (a[i] <= b[j]) out.push_back(a[i++]);    // <= keeps it stable
        else out.push_back(b[j++]);
    }
    while (i < a.size()) out.push_back(a[i++]);     // copy whatever is left
    while (j < b.size()) out.push_back(b[j++]);
    return out;
}

int main() {
    for (int x : merge({1, 4, 9, 10}, {2, 3, 9, 20, 21})) std::cout << x << " ";
    std::cout << "\n";
}

1 2 3 4 9 9 10 20 21 

Why O(n log n)

Halving repeatedly gives about log₂ n levels of recursion. At each level, the merges together touch every element once, which is O(n) work per level. So the total is O(n log n), and unlike quicksort that's true even in the worst case.

[5 2 8 1 9 3]
[5 2 8] [1 9 3]          split
[5] [2 8] [1] [9 3]      split
...                      single elements are sorted
[2 5 8] [1 3 9]          merge
[1 2 3 5 8 9]            merge

Properties

• Always O(n log n).
• Stable, as long as the merge takes from the left half on ties (<=). That's why std::stable_sort is usually a merge sort.
• Needs O(n) extra memory for merging.

Your task

Write a recursive helper that sorts v[lo..hi): if the range has fewer than 2 elements, return; otherwise sort both halves and merge them through a temporary vector, copying the result back. Allocating one temporary buffer up front and reusing it is faster than making new vectors at every level.

Your turn: implement merge_sort(std::vector<int>& v). The test sorts 200,000 numbers, so an O(n²) sort won't finish in time.

Previous: Insertion sort Next: Quicksort and partitioning