Merge SortMerge sort

01Why it exists

Reach for it when you see:Does not fit in memory, external sorting, a stable sort is required, n log n even in the worst case, sorting a linked list, merging two sorted runs, inversions or "how many elements to my right are smaller".

02The core idea

To combine two runs that are already sorted, point one pointer at the head of each, compare, write the smaller value to the output, and advance that side. n elements take n writes, so the merge is O(n). Merge sort turns sorting into merging: cut the array down the middle, sort each half recursively, then merge. Keep cutting until a piece holds 0 or 1 element, which is sorted by definition — that is the base case.

Correctness follows by induction: assume both halves are sorted when the recursive calls return, and the whole range is sorted as long as the merge itself is correct. The merge's invariant is that the k elements already written to the output are the k smallest across both runs, in order. Each run is sorted on its own, so the smallest remaining element has to be one of the two the pointers are looking at; writing the smaller of them preserves the invariant, and when the output is full the range is done. Stability comes from writing the comparison as a[i] <= a[j]: on a tie it takes the left run, and elements in the left run came earlier in the original array. Writing < takes the right one first, which still produces a sorted result but throws stability away.

Complexity: T(n) = 2T(n/2) + O(n). Drawn as a recursion tree, level d holds 2^d runs of length n/2^d, so all the merges on that level together handle exactly n elements, and it takes ⌈log₂ n⌉ levels to cut down to length 1 — O(n log n) in total. The split ignores the data, so the best, average and worst cases are all O(n log n); the number of comparisons in a single merge lies between the length of the shorter run and len − 1, which only moves the constant. Add the check that skips the merge when a[mid-1] <= a[mid] and an already-sorted input drops to O(n). Space: merging needs a scratch array, and one shared buffer of O(n) serves the entire sort, plus O(log n) for the recursion stack. The bottom-up iterative version drops the recursion, but the scratch array is still O(n).

Common mistakes: slicing out fresh arrays at every recursive call (a[:mid], a[mid:]) does not change the complexity, but it allocates over and over and carries a heavy constant — allocate one shared buffer up front instead. Mixing open and closed ranges is the other one: [lo, mid) and [mid, hi) together with hi - lo <= 1 form one consistent set, and switching to closed ranges means changing all of them, or you will skip cells or recurse forever. Against its neighbours: quicksort is in place, cache-friendly and usually faster on average, but its worst case is O(n²) and it is not stable; heapsort needs only O(1) space and is also unstable. Merge sort spends O(n) space to buy stability plus an O(n log n) worst case. Insertion sort is genuinely faster on short runs, which is why TimSort tidies short runs with insertion sort before merging them. The merge step itself only rewrites pointers on a linked list (see merging lists), and counting as you merge is how you get inversions.

03The algorithm

1. 1Define sort(lo, hi): it sorts the half-open range [lo, hi). When hi - lo <= 1 it returns immediately, which is the base case.
2. 2mid = (lo + hi) // 2, then recurse into sort(lo, mid) and sort(mid, hi). Both halves are sorted by the time those calls return.
3. 3Merge: set i = lo and j = mid, compare a[i] with a[j], write the smaller one into the scratch array, and advance that side's pointer. Take the left one on ties (<=) to stay stable.
4. 4Once one run runs out, whatever is left in the other is already sorted, so copy it across in one go. Finally write [lo, hi) of the scratch array back into the original array.
5. 5Allocate the scratch array once at the outermost level and share it across every merge. Do not build a new array at each level.
6. 6Refinements worth making in practice: when a[mid-1] <= a[mid] the two runs already line up, so skip the merge; for very short runs (a dozen elements or so) switch to insertion sort. If you would rather avoid recursion, go bottom-up and merge runs of width 1, 2, 4 and so on, one pass at a time.

04Interactive demo

One shared array, [5, 2, 9, 1, 7, 3, 8, 4]. The four rows are recursion levels 0 to 3: a split moves a whole run down one level, and a merge pulls elements back up one at a time, with a dashed cell meaning that position's value currently lives on another level. Yellow marks the two run pointers during a merge, blue is the position just written to the output, and green marks a run that is already sorted. Count the comparisons: level 2 does four merges of 1 each, level 1 two merges of 3 each, and level 0 takes 7 — 17 in total, and never more than n = 8 on any single level.

05Code

The top-down recursive version and the bottom-up iterative version share one merge function. The recursive one maps directly onto the steps above; the iterative one drops the recursion and merges runs of width 1, 2, 4 and so on, one pass at a time — the same shape as external sorting merging its temporary files pass by pass. Both allocate the scratch array once and use <= to stay stable. The last example uses order data to show stability, with the C++ side comparing against the standard library's std::stable_sort.

# Merge the sorted runs src[lo:mid] and src[mid:hi] into dst[lo:hi]
def merge(src, dst, lo, mid, hi, key):
    i, j = lo, mid
    for k in range(lo, hi):
        # Take from the left if it still has elements and either the right is done or left <= right; taking the left on ties is what keeps it stable
        if i < mid and (j == hi or key(src[i]) <= key(src[j])):
            dst[k] = src[i]
            i += 1
        else:
            dst[k] = src[j]
            j += 1


# Top-down: split in half, sort each half recursively, merge. Half-open range [lo, hi)
def merge_sort(a, key=lambda x: x):
    buf = a[:]                              # the scratch array is allocated once and shared by every merge

    def sort(lo, hi):
        if hi - lo <= 1:                    # 0 or 1 element is already sorted
            return
        mid = (lo + hi) // 2
        sort(lo, mid)
        sort(mid, hi)
        if key(a[mid - 1]) <= key(a[mid]):  # the two runs already line up, so skip the merge
            return
        merge(a, buf, lo, mid, hi, key)
        for k in range(lo, hi):             # write the merged result back into the array
            a[k] = buf[k]

    sort(0, len(a))
    return a


# Bottom-up: no recursion. Runs of width 1, 2, 4, 8... merged in pairs, one pass at a time
def merge_sort_bottom_up(a, key=lambda x: x):
    n = len(a)
    src, dst = a, [None] * n                # only one extra array is allocated
    width = 1
    while width < n:
        for lo in range(0, n, 2 * width):
            merge(src, dst, lo, min(lo + width, n), min(lo + 2 * width, n), key)
        src, dst = dst, src                 # this pass's output is the next pass's input
        width *= 2
    if src is not a:                        # the result ended up in the scratch array, so copy it back
        a[:] = src
    return a


if __name__ == "__main__":
    print(merge_sort([5, 2, 9, 1, 7, 3, 8, 4]))            # [1, 2, 3, 4, 5, 7, 8, 9]
    print(merge_sort_bottom_up([5, 2, 9, 1, 7, 3, 8, 4]))  # [1, 2, 3, 4, 5, 7, 8, 9]
    # Stability: the orders are already in time order, and after sorting by status each status keeps that order
    orders = [("A01", "shipped"), ("A02", "pending"), ("A03", "shipped"), ("A04", "pending")]
    print(merge_sort(orders, key=lambda o: o[1]))
    # [('A02', 'pending'), ('A04', 'pending'), ('A01', 'shipped'), ('A03', 'shipped')]

06Practice

• LeetCode 2570Merge Two 2D Arrays by Summing Values (practise the merge step on its own)Easy
• LeetCode 912Sort an Array (write it once top-down and once bottom-up)Medium
• LeetCode 148Sort List (the linked-list version; bottom-up reaches O(1) extra space)Medium
• LeetCode 937Reorder Data in Log Files (relies on a stable sort)Medium
• LeetCode 315Count of Smaller Numbers After Self (count while merging)Hard
• LeetCode 493Reverse Pairs (count with two pointers before merging)Hard