Merge Sort

Divide and conquer

Merge sort solves a big problem by breaking it into smaller copies of itself:

1. Divide: cut the array into two halves.
2. Conquer: sort each half — using merge sort again (recursion!).
3. Combine: merge the two sorted halves into one sorted array.

The recursion stops when a piece has just one element — a single element is already sorted.

Analogy: sorting a huge pile of exam papers with friends. Split the pile in two and give each half to a friend; they split theirs again, and so on. When everyone holds one paper, you start combining sorted piles back together.

The merge step — the heart of the algorithm

Merging two already sorted lists is easy and fast. Look at the front of both lists, take the smaller one, and repeat:

L = [2, 7, 9]     R = [3, 4, 10]
compare 2 vs 3  → take 2    result: [2]
compare 7 vs 3  → take 3    result: [2, 3]
compare 7 vs 4  → take 4    result: [2, 3, 4]
compare 7 vs 10 → take 7    result: [2, 3, 4, 7]
compare 9 vs 10 → take 9    result: [2, 3, 4, 7, 9]
L is empty      → copy 10   result: [2, 3, 4, 7, 9, 10]

Every comparison places one element, so merging n elements costs O(n).

Seeing recursion in 3D

In the model, the depth of the recursion is real depth. When an array is split, both halves step towards you (cyan = left half, purple = right half). When two halves are merged, the elements step back one level, one by one, in sorted order — exactly like a recursive call returning to its caller. When everything is back on the original row, the array is sorted.

Why O(n log n)?

• You can halve n only about log₂ n times before reaching size 1 — so there are log₂ n levels.
• On each level, all the merges together touch each of the n elements once — O(n) per level.
• Total: O(n log n), and this holds for every input. Sorted, reversed, random — it doesn’t matter.

Code

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:        # <= keeps the sort stable
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])            # copy whatever is left
    result.extend(right[j:])
    return result

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))   # [3, 9, 10, 27, 38, 43, 82]

#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int>& a, int lo, int mid, int hi) {
    vector<int> tmp;
    int i = lo, j = mid + 1;
    while (i <= mid && j <= hi)
        tmp.push_back(a[i] <= a[j] ? a[i++] : a[j++]);
    while (i <= mid) tmp.push_back(a[i++]);
    while (j <= hi)  tmp.push_back(a[j++]);
    for (int k = 0; k < (int)tmp.size(); k++) a[lo + k] = tmp[k];
}

void mergeSort(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;               // 0 or 1 element
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid);
    mergeSort(a, mid + 1, hi);
    merge(a, lo, mid, hi);
}

int main() {
    vector<int> a = {38, 27, 43, 3, 9, 82, 10};
    mergeSort(a, 0, a.size() - 1);
    for (int x : a) cout << x << " ";   // 3 9 10 27 38 43 82
}

Properties

Where is it used?

• Sorting linked lists — merging needs no random access, so it is ideal.
• External sorting — data too large for RAM is sorted in chunks and merged from disk.
• Python’s built-in sorted() and Java’s object sort use Timsort, a hybrid of merge sort and insertion sort.
• Counting inversions in an array (a popular interview problem) is a small change to merge sort.

Common mistakes

• Forgetting to copy the leftovers after one half runs out.
• Using < instead of <= in the merge, which breaks stability.
• Wrong base case (lo > hi instead of lo >= hi), causing infinite recursion.