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 task

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

Challenge 2

An inversion is a pair i < j with v[i] > v[j]. Write long long count_inversions(std::vector<int> v) in O(n log n) by merge sorting and counting while you merge: when an element from the right half is taken before the remaining left elements, it forms an inversion with each of them.

Challenge 3

Write std::vector<int> merge_all(const std::vector<std::vector<int>>& lists) that merges any number of sorted lists into one sorted list by divide and conquer: merge the left half of the lists, merge the right half, then merge those two results. Write the two-list merge yourself.

Previous: Insertion sort Next: Quicksort and partitioning