On this page

Merge Sort & Inversion Counting

Merge sort is the cleanest divide-and-conquer algorithm there is: split the array in half, sort each half, merge the two sorted halves. Every part of it can be analysed exactly. It is stable, its worst case is with no probability involved, it is the natural sort for linked lists and for data that does not fit in memory, and its merge step — two pointers walking two sorted sequences — is one of the most reused ideas in computing. Database sort-merge joins, LSM-tree compaction, external sorting, Timsort and the Linux kernel's list sorting are all merges at heart.

The second half of this page is about what merge sort computes along the way. While merging, every time an element of the right half overtakes elements of the left half, it reveals exactly how many inversions it was part of. That turns merge sort into an algorithm for counting inversions, and the same trick solves a family of "count the pairs such that…" problems: count of smaller numbers after self, reverse pairs, count of range sum.

Why this exists

The elementary sorts are quadratic for a structural reason: each adjacent swap removes at most one inversion, and a random array has of them. To do better an algorithm must fix many inversions per step. Merge sort does it by never comparing elements that are already known to be in order: once the two halves are sorted, a single linear pass merges them, and that pass implicitly resolves every inversion between the halves — up to of them — in comparisons or fewer.

John von Neumann described merge sort in 1945, in his work on the EDVAC; it is one of the first algorithms ever written for a stored-program computer. It came out of the needs of the time: data lived on magnetic tape, which can only be read sequentially, and merging is the one sorting operation that needs nothing but sequential reads and writes. That property is why merge sort, in its external form, is still how databases and MapReduce frameworks sort data larger than RAM. Knuth's Volume 3 (§5.2.4 for internal merging, §5.4 for external) is the classic treatment.

In memory, merge sort competes with quicksort and usually loses on raw speed for arrays of primitives, because it needs an auxiliary buffer and moves every element at every level. It wins whenever stability or a guaranteed worst case matters, whenever the data is a linked list, and whenever the input already contains sorted runs — which is why Python, Java (for objects), JavaScript engines and Android all sort with Timsort, a run-adaptive merge sort.

Pattern triggers

If the problem says or has…Think of…
"Sort a linked list", "in time and extra space"Bottom-up merge sort on the list (LeetCode 148)
"Stable sort", "keep the original order of equal elements", guaranteed worst caseMerge sort (or the library's stable sort, which is merge-based)
"Count pairs with ", "number of inversions", "minimum adjacent swaps"Merge sort with a counter: add mid - i whenever the right element wins
"For each element, count the smaller elements to its right"Merge sort on indices, accumulating per element (LeetCode 315)
"Count pairs with " for a monotone conditionCount across halves with two pointers before merging (reverse pairs, range sums)
"Merge sorted lists / files / streams"-way merge with a min-heap,
"The data does not fit in memory", "sort a 100 GB file with 1 GB of RAM"External merge sort: sorted runs, then -way merges
"Already partly sorted", "concatenation of sorted blocks"Natural merge sort / Timsort: merge the existing runs
"Kendall tau distance", "how different are two rankings"Inversions of one ranking relative to the other

Intuition & first principles

The merge

Suppose two piles of exam papers are each sorted by score. To produce one sorted pile, look at the top paper of each pile, take the lower-scored one, and repeat. Each step does one comparison and outputs one paper; when a pile runs out, the rest of the other pile goes on unchanged. Two sorted piles of sizes and merge in at most comparisons.

Precisely: merge takes sorted L[0..m-1] and R[0..k-1] and produces their sorted union. It keeps indices and ; while both are in range it outputs L[i] if L[i] <= R[j], else R[j], advancing that index; then it copies whatever remains. This is Family C of Two Pointers. The <= (ties go to the left) is what makes the merge — and therefore merge sort — stable: among equal keys, everything from the left half, which came earlier in the input, is output first.

Divide and conquer

Merge needs sorted inputs. Where do they come from? Recursively: an array of length 0 or 1 is sorted; any longer array is split at , both halves are sorted recursively, and the results are merged. That is top-down merge sort.

You can also build it from the bottom: every single element is a sorted run of length 1; merge neighbouring runs pairwise into runs of length 2, then 4, then 8, until one run covers the array. That is bottom-up merge sort. It does the same kind of work with no recursion at all, which makes it the natural form for linked lists, for external sorting, and for anyone worried about stack depth.

What a merge learns about inversions

When the merge outputs R[j] while L[i..m-1] are still waiting, R[j] is smaller than every one of those waiting elements (they are sorted, and L[i] > R[j]). Each of them came before R[j] in the original array, so each forms an inversion with it. Adding to a counter at that moment counts every inversion between the two halves exactly once. Inversions within each half were counted by the recursive calls. That is the whole inversion-counting algorithm: merge sort plus one line.

Mechanics

Top-down merge sort

flowchart TD
    R["[38, 27, 43, 3, 9, 82, 10]<br/>→ [3, 9, 10, 27, 38, 43, 82]"] --> A["[38, 27, 43]<br/>→ [27, 38, 43]"]
    R --> B["[3, 9, 82, 10]<br/>→ [3, 9, 10, 82]"]
    A --> A1["[38]"]
    A --> A2["[27, 43]<br/>→ [27, 43]"]
    A2 --> A21["[27]"]
    A2 --> A22["[43]"]
    B --> B1["[3, 9]<br/>→ [3, 9]"]
    B --> B2["[82, 10]<br/>→ [10, 82]"]
    B1 --> B11["[3]"]
    B1 --> B12["[9]"]
    B2 --> B21["[82]"]
    B2 --> B22["[10]"]

Each node splits on the way down (at ) and merges on the way up; the arrow inside a label shows the node's merged result. The merges happen in post-order. Trace of the six merges on [38, 27, 43, 3, 9, 82, 10] (computed by script; "cross inversions" is the mid - i counter):

Merge #Left runRight runComparisonsCross inversionsResult
1[27][43]10[27, 43]
2[38][27, 43]21[27, 38, 43]
3[3][9]10[3, 9]
4[82][10]11[10, 82]
5[3, 9][10, 82]20[3, 9, 10, 82]
6[27, 38, 43][3, 9, 10, 82]69[3, 9, 10, 27, 38, 43, 82]

Totals: 13 comparisons and 11 inversions. Merge 5 needed only 2 comparisons because the left run [3, 9] was exhausted after two steps; the right run was then copied with no comparisons. Merge 6 found 9 inversions: each of 3, 9 and 10 overtook all three elements of [27, 38, 43].

Bottom-up merge sort

flowchart LR
    P0["width 1:<br/>[38] [27] [43] [3] [9] [82] [10]"] --> P1["width 2:<br/>[27, 38] [3, 43] [9, 82] [10]"]
    P1 --> P2["width 4:<br/>[3, 27, 38, 43] [9, 10, 82]"]
    P2 --> P3["width 8:<br/>[3, 9, 10, 27, 38, 43, 82]"]

Pass with width merges a[lo..lo+w-1] with a[lo+w..lo+2w-1] for , clipping the right run at ; a final run with no partner is carried over unchanged. Trace (computed by script):

WidthLeft runRight runComparisonsCross inversionsMerged
1[38][27]11[27, 38]
1[43][3]11[3, 43]
1[9][82]10[9, 82]
1[10]—00carried over
2[27, 38][3, 43]32[3, 27, 38, 43]
2[9, 82][10]21[9, 10, 82]
4[3, 27, 38, 43][9, 10, 82]66[3, 9, 10, 27, 38, 43, 82]

Totals: 14 comparisons and 11 inversions. The inversion count is a property of the input, so both versions find 11; the comparison count depends on how the array is split, so top-down (13) and bottom-up (14) differ. For a power of two the two versions split identically.

The last merge, step by step:

StepijL[i]R[j]OutputInversions added
100393 (left)0
2102799 (right)3 (27, 38, 43 are waiting)
311271010 (right)3
412278227 (left)0
522388238 (left)0
632438243 (left)0
—42—82copy 820
Bottom-up merge sort doubles the run width each pass; every level does O(n) merge work and there are log₂ n levels, so the total is O(n log n).

Memory layout of a practical merge

A textbook merge allocates new lists at every call. A practical one allocates a single auxiliary buffer aux of size once. To merge a[lo..mid-1] with a[mid..hi-1]: copy a[lo..hi-1] into aux[lo..hi-1], then merge from aux back into a. Two refinements are common:

  • Skip the merge if the halves are already in order: if a[mid-1] <= a[mid], the concatenation is sorted. This one comparison makes merge sort run in on sorted input (each level costs one comparison per merge) and is in most production implementations.
  • Copy only the left half: copy a[lo..mid-1] into a buffer of size and merge forward into a; the right half never needs copying because the write position can never overtake the unread right elements. This halves both the buffer and the copying. Timsort uses this, copying whichever run is smaller.

The ladder: brute force → better → optimal

The task: sort comparable elements (and, for the second half of the page, count inversions).

Rung 1 — quadratic sort, . Insertion sort sorts and, as proved in the previous lesson, its number of shifts is the inversion count. For counting inversions the brute force is the double loop over all pairs, comparisons. At that is about — too slow for a 1-second limit in any language.

Rung 2 — split once, . Insertion-sort the two halves separately ( shifts on average instead of ), then merge them in comparisons. Halving once halves the quadratic work. This is the key observation: sorting is superadditive, so splitting pays.

Rung 3 — split recursively, . If splitting once halves the work, split the halves too, all the way down to single elements. Now the work is the merging alone: about per level, levels. For : about comparisons instead of . Counting inversions comes free with one extra addition per merge step.

Rung 4 — engineering the constant. Allocate one buffer, not one per call; insertion-sort runs below about 16–32 elements (recursion overhead dominates there); skip merges whose halves are already in order; copy only the smaller run; detect natural runs. These give no asymptotic gain but routinely make merge sort 2–3 times faster, and the last two make it adaptive. Fully engineered, this rung is Timsort, the subject of Sorting in the Real World.

Rung 5 — the lower bound. No comparison sort can beat comparisons in the worst case (Non-Comparison Sorts & the Lower Bound). Merge sort's worst case is , within about of that bound when is a power of two. In comparisons, merge sort is essentially optimal; what it pays for is memory traffic.

RungSort timeInversion count timeExtra spaceStableNotes
Insertion sort / pair loopyesFine for a few thousand
Split once + merge shiftsyesShows why splitting pays
Merge sortyesWorst case guaranteed
Engineered (Timsort), on runs—yesWhat libraries ship
Lower bound for comparison-based methods——Merge sort is within of it

Correctness

The merge invariant

Lemma (merge). Let L[0..m-1] and R[0..k-1] be sorted. At the start of each iteration of the merge loop, the output out[0..i+j-1] is sorted and consists of the smallest elements of the multiset — specifically L[0..i-1] and R[0..j-1] — and every element of out is every element of L[i..] and R[j..].

Initialisation. , out is empty.

Maintenance. Suppose both L[i] and R[j] exist and L[i] <= R[j]. Since L is sorted, L[i] is the smallest of L[i..]; since R is sorted and L[i] <= R[j], it is also everything in R[j..]. So L[i] is a minimum of the remaining elements, and by the invariant it is everything already output. Appending it keeps out sorted and preserves both parts of the invariant. The case L[i] > R[j] is symmetric.

Termination. Each iteration increases by one. When one input is exhausted, the remainder of the other is sorted and, by the invariant, everything in out; appending it gives the sorted union.

Stability of the merge. Take two elements with equal keys. If both come from the same input, they are output in their order within that input (each input is consumed front to back). If comes from L and from R, then when both are at the front, L[i] <= R[j] holds, so goes first. Since L is the left half — earlier in the original array — equal keys keep their original order. Using < instead of <= sends first and breaks stability while still sorting.

Merge sort

Theorem. Top-down merge sort returns the elements of a[lo..hi-1] in sorted order, and does so stably.

Proof by strong induction on . For the range is already sorted and the algorithm returns it unchanged. For , gives two ranges of sizes and , both at least 1 and strictly less than . By the induction hypothesis the recursive calls sort them stably. By the merge lemma the merge produces their sorted union, stably, with the left range's elements first among equals — which, combined with the stability of each half, preserves the original relative order of every pair of equal keys.

Bottom-up merge sort is proved by an invariant on passes: before the pass with width , each block a[t·w .. (t+1)·w - 1] (the last one possibly shorter) is sorted. For it is trivial; the merge lemma takes it from to ; the loop stops when , when the single block is the whole array.

Inversion counting

Theorem. Merge sort with the counter inv += mid - i (added whenever the right element is output) returns , the number of pairs with .

Proof by strong induction. Partition the inversions of a[lo..hi-1] into three classes: both indices in the left half, both in the right half, and cross inversions with in the left half and in the right. The recursive calls count the first two classes (induction hypothesis). Sorting each half does not change which cross pairs are inversions, because it only permutes elements within a half — every left element still precedes every right element in the original order. So it remains to show that the merge counts cross inversions exactly.

Fix a right element . When the merge outputs from position R[j], the elements still waiting in the left run are L[i..m-1]. Every one of them is : L[i] > R[j] triggered the right branch, and L is sorted. Every left element already output, L[0..i-1], is : each was output while (or a smaller right element) was waiting, which required it to be that element. So the left elements greater than are exactly L[i..m-1], and = mid - i is the number of cross inversions whose second element is . If is output in the copy-the-rest phase, the left run is empty and the count is right. Summing over all right elements counts every cross inversion exactly once.

Note the role of <=: with equal keys, the left copy is output first, so an equal pair is not counted. That matches the definition (strict ). Using < would count equal pairs as inversions.

Complexity

The recurrence

Let be the worst-case number of comparisons. The two recursive calls cost and the merge at most :

For a quick asymptotic answer, write the simplified recurrence and solve it two ways (see Complexity Analysis for both methods).

Recursion tree. The root costs . Its two children cost each — in total. The four grandchildren cost each — again. Level has subproblems of size , total cost . The leaves are at depth . So the total is per level times levels: exactly when is a power of two (with ).

flowchart TD
    L0["level 0: one problem of size n<br/>cost n"] --> L1["level 1: 2 problems of size n/2<br/>cost 2 × n/2 = n"]
    L1 --> L2["level 2: 4 problems of size n/4<br/>cost 4 × n/4 = n"]
    L2 --> LD["level d: 2^d problems of size n/2^d<br/>cost n"]
    LD --> LL["level lg n: n leaves of size 1<br/>cost 0"]
    LL --> TOT["total: n per level × lg n levels = n lg n"]

Master theorem. For with , : , and . That is case 2, which gives . The intuition matches the tree: when the work per level is constant, the answer is (work per level) × (number of levels).

Exact comparison counts

  • Merging sorted runs of sizes and takes between comparisons (one run is entirely smaller than the other) and (the runs interleave to the end).
  • Worst case of top-down merge sort: . For : ; for : 8,977; for : . This was checked by enumerating all permutations for . Curiously, it is exactly the number of comparisons binary insertion sort makes, — two very different algorithms with identical worst-case comparison counts.
  • Best case for : , when every merge finds one run entirely below the other (for example, already sorted input without the skip-merge check). For : 12.
  • Average case: about ; the precise coefficient oscillates slightly with (Flajolet and Golin, 1994). Measured over 50 random permutations of 1,024 elements: 8,947 comparisons on average, against .
  • Lower bound for any comparison sort: , which is . For : against merge sort's worst case 8,977 — within 5.3%.

Top-down and bottom-up have the same worst case when is a power of two. For other bottom-up can be slightly worse, because its last merge can be badly unbalanced (a run of against a short remainder): on the 7-element example it used 14 comparisons to top-down's 13.

Space

  • Auxiliary array: for the standard array merge (or when only one run is copied). This is merge sort's main cost and the reason it is not used for primitives in most libraries.
  • Stack: top-down recursion depth is , so — about 30 frames for a billion elements, never a problem. Bottom-up uses .
  • Linked lists: extra space (bottom-up) or (top-down recursion), because merging two lists only relinks nodes. See Variations.

In-place merging: possible, rarely worth it

Can the merge be done without the buffer? Yes, but at a price:

  • Rotation-based merge: find the median of the left run, binary-search its position in the right run, rotate the middle block, recurse on both sides. per merge, for the whole sort. This is what std::inplace_merge and std::stable_sort fall back to when they cannot allocate a buffer — the standard specifies for stable_sort with enough memory and without.
  • Linear-time stable in-place merging exists (Kronrod 1969; Huang and Langston, "Practical In-Place Merging", CACM 1988), and block merge sorts such as WikiSort and GrailSort build an in-place stable sort on it. The constants are large and the code is long; libraries prefer to allocate.

Constants and cache behaviour

Merge sort reads and writes memory sequentially: each merge streams two input runs and one output run, a pattern hardware prefetchers handle at close to memory bandwidth. That makes merge sort cache-friendly in the sense of avoiding random access, but it moves every element at every level — element moves, plus the copying into aux — whereas quicksort moves only the elements that are on the wrong side of a pivot. For large arrays of small keys that extra memory traffic is why a well-implemented quicksort is typically faster. For arrays of pointers to large objects, or when comparisons are expensive (strings, user-defined comparators), the balance shifts towards merge sort, which does fewer comparisons than quicksort on average ( against quicksort's ). The cache-oblivious refinement is to merge in blocks that fit in cache, or to use a multiway merge; external sorting takes that idea to disk.

Implementation

The canonical block implements top-down and bottom-up merge sort generically with a comparator and a single auxiliary buffer; both return the inversion count they discover along the way. Tests: the trace input, edge cases, stability on records, and a randomised comparison against the built-in sort and a brute-force inversion count.

import random
from typing import Any, Callable


def identity(x: Any) -> Any:
    return x


def merge(a: list, aux: list, lo: int, mid: int, hi: int, key: Callable) -> int:
    """Merge sorted a[lo:mid] and a[mid:hi] in place via aux. Return the cross inversions."""
    aux[lo:hi] = a[lo:hi]
    i, j, inv = lo, mid, 0
    for k in range(lo, hi):
        if i < mid and (j >= hi or key(aux[i]) <= key(aux[j])):   # <= : ties go left -> stable
            a[k] = aux[i]
            i += 1
        else:
            a[k] = aux[j]
            j += 1
            inv += mid - i                       # aux[i:mid] are all > this element
    return inv


def merge_sort(a: list, key: Callable = identity) -> int:
    """Top-down merge sort, stable, in place. Returns the number of inversions."""
    aux = list(a)

    def sort(lo: int, hi: int) -> int:
        if hi - lo <= 1:
            return 0
        mid = (lo + hi) // 2
        inv = sort(lo, mid) + sort(mid, hi)
        if key(a[mid - 1]) <= key(a[mid]):       # halves already in order: no cross inversions
            return inv
        return inv + merge(a, aux, lo, mid, hi, key)

    return sort(0, len(a))


def merge_sort_bottom_up(a: list, key: Callable = identity) -> int:
    """Bottom-up merge sort, stable, no recursion. Returns the number of inversions."""
    n = len(a)
    aux = list(a)
    inv, width = 0, 1
    while width < n:
        for lo in range(0, n - width, 2 * width):   # only blocks that have a right partner
            mid, hi = lo + width, min(lo + 2 * width, n)
            inv += merge(a, aux, lo, mid, hi, key)
        width *= 2
    return inv


def inversions_naive(a: list) -> int:
    return sum(1 for i in range(len(a)) for j in range(i + 1, len(a)) if a[i] > a[j])


if __name__ == "__main__":
    trace = [38, 27, 43, 3, 9, 82, 10]
    for sort in (merge_sort, merge_sort_bottom_up):
        b = list(trace)
        assert sort(b) == 11 and b == [3, 9, 10, 27, 38, 43, 82]
        for data, inv in (([], 0), ([1], 0), ([2, 2, 2], 0), ([5, 2, 4, 6, 1, 3], 9),
                          (list(range(8, 0, -1)), 28), (list(range(10)), 0)):
            b = list(data)
            assert sort(b) == inv and b == sorted(data), (sort.__name__, data)

        recs = [(4, "a"), (2, "b"), (4, "c"), (1, "d"), (2, "e")]
        b = list(recs)
        sort(b, key=lambda r: r[0])
        assert b == [(1, "d"), (2, "b"), (2, "e"), (4, "a"), (4, "c")]   # stable

    rng = random.Random(7)
    for _ in range(300):
        n = rng.randint(0, 40)
        data = [(rng.randint(0, 9), idx) for idx in range(n)]
        keys = [r[0] for r in data]
        expected = sorted(data, key=lambda r: r[0])
        for sort in (merge_sort, merge_sort_bottom_up):
            b = list(data)
            sort(b, key=lambda r: r[0])
            assert b == expected
            k = list(keys)
            assert sort(k) == inversions_naive(keys)
    print("ok")
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;

public class MergeSort {
    record Rec(int key, char tag) {}

    /** Merge sorted a[lo..mid-1] and a[mid..hi-1] via aux. Returns the cross inversions. */
    static <T> long merge(T[] a, T[] aux, int lo, int mid, int hi, Comparator<? super T> c) {
        System.arraycopy(a, lo, aux, lo, hi - lo);
        int i = lo, j = mid;
        long inv = 0;
        for (int k = lo; k < hi; k++) {
            if (i < mid && (j >= hi || c.compare(aux[i], aux[j]) <= 0)) {   // ties go left: stable
                a[k] = aux[i++];
            } else {
                a[k] = aux[j++];
                inv += mid - i;
            }
        }
        return inv;
    }

    static <T> long sort(T[] a, T[] aux, int lo, int hi, Comparator<? super T> c) {
        if (hi - lo <= 1) return 0;
        int mid = (lo + hi) >>> 1;
        long inv = sort(a, aux, lo, mid, c) + sort(a, aux, mid, hi, c);
        if (c.compare(a[mid - 1], a[mid]) <= 0) return inv;            // already in order
        return inv + merge(a, aux, lo, mid, hi, c);
    }

    /** Top-down merge sort, stable. Returns the number of inversions. */
    static <T> long mergeSort(T[] a, Comparator<? super T> c) {
        return sort(a, a.clone(), 0, a.length, c);
    }

    /** Bottom-up merge sort, stable, no recursion. Returns the number of inversions. */
    static <T> long mergeSortBottomUp(T[] a, Comparator<? super T> c) {
        int n = a.length;
        T[] aux = a.clone();
        long inv = 0;
        for (int width = 1; width < n; width *= 2) {
            for (int lo = 0; lo < n - width; lo += 2 * width) {
                int mid = lo + width, hi = Math.min(lo + 2 * width, n);
                inv += merge(a, aux, lo, mid, hi, c);
            }
        }
        return inv;
    }

    static long inversionsNaive(Integer[] a) {
        long cnt = 0;
        for (int i = 0; i < a.length; i++) for (int j = i + 1; j < a.length; j++) if (a[i] > a[j]) cnt++;
        return cnt;
    }

    static void check(boolean ok, String msg) {
        if (!ok) throw new AssertionError(msg);
    }

    static Integer[] box(int... xs) {
        return Arrays.stream(xs).boxed().toArray(Integer[]::new);
    }

    static <T> long run(int which, T[] a, Comparator<? super T> c) {
        return which == 0 ? mergeSort(a, c) : mergeSortBottomUp(a, c);
    }

    public static void main(String[] args) {
        Comparator<Integer> nat = Comparator.naturalOrder();
        Comparator<Rec> byKey = Comparator.comparingInt(Rec::key);
        int[][] cases = {{}, {1}, {2, 2, 2}, {5, 2, 4, 6, 1, 3}, {8, 7, 6, 5, 4, 3, 2, 1}, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}};
        long[] invs = {0, 0, 0, 9, 28, 0};
        for (int w = 0; w < 2; w++) {
            Integer[] t = box(38, 27, 43, 3, 9, 82, 10);
            check(run(w, t, nat) == 11, "trace inversions");
            check(Arrays.equals(t, box(3, 9, 10, 27, 38, 43, 82)), "trace sorted");
            for (int k = 0; k < cases.length; k++) {
                Integer[] b = box(cases[k]);
                Integer[] expected = box(cases[k]);
                Arrays.sort(expected);
                check(run(w, b, nat) == invs[k], "inversions case " + k);
                check(Arrays.equals(b, expected), "sorted case " + k);
            }
            Rec[] recs = {new Rec(4, 'a'), new Rec(2, 'b'), new Rec(4, 'c'), new Rec(1, 'd'), new Rec(2, 'e')};
            run(w, recs, byKey);
            check(Arrays.equals(recs, new Rec[]{new Rec(1, 'd'), new Rec(2, 'b'), new Rec(2, 'e'),
                    new Rec(4, 'a'), new Rec(4, 'c')}), "stable");
        }
        Random rng = new Random(7);
        for (int t = 0; t < 300; t++) {
            int n = rng.nextInt(41);
            Rec[] data = new Rec[n];
            Integer[] keys = new Integer[n];
            for (int i = 0; i < n; i++) {
                data[i] = new Rec(rng.nextInt(10), (char) ('A' + i));
                keys[i] = data[i].key();
            }
            Rec[] expected = data.clone();
            Arrays.sort(expected, byKey);                                 // stable TimSort
            for (int w = 0; w < 2; w++) {
                Rec[] b = data.clone();
                run(w, b, byKey);
                check(Arrays.equals(b, expected), "random stable sort");
                check(run(w, keys.clone(), nat) == inversionsNaive(keys), "random inversions");
            }
        }
        System.out.println("ok");
    }
}
#include <algorithm>
#include <cstddef>
#include <functional>
#include <iostream>
#include <random>
#include <vector>

// comp(x, y) is a strict "x before y". Merges a[lo..mid) and a[mid..hi) via aux.
template <class T, class Comp>
long long mergeRuns(std::vector<T>& a, std::vector<T>& aux, std::size_t lo, std::size_t mid,
                    std::size_t hi, Comp comp) {
    std::copy(a.begin() + lo, a.begin() + hi, aux.begin() + lo);
    std::size_t i = lo, j = mid;
    long long inv = 0;
    for (std::size_t k = lo; k < hi; ++k) {
        if (i < mid && (j >= hi || !comp(aux[j], aux[i]))) {   // aux[i] <= aux[j]: ties go left
            a[k] = aux[i++];
        } else {
            a[k] = aux[j++];
            inv += static_cast<long long>(mid - i);
        }
    }
    return inv;
}

template <class T, class Comp>
long long sortRange(std::vector<T>& a, std::vector<T>& aux, std::size_t lo, std::size_t hi, Comp comp) {
    if (hi - lo <= 1) return 0;
    std::size_t mid = lo + (hi - lo) / 2;
    long long inv = sortRange(a, aux, lo, mid, comp) + sortRange(a, aux, mid, hi, comp);
    if (!comp(a[mid], a[mid - 1])) return inv;                // already in order
    return inv + mergeRuns(a, aux, lo, mid, hi, comp);
}

template <class T, class Comp = std::less<T>>
long long mergeSort(std::vector<T>& a, Comp comp = Comp{}) {
    std::vector<T> aux(a);
    return sortRange(a, aux, 0, a.size(), comp);
}

template <class T, class Comp = std::less<T>>
long long mergeSortBottomUp(std::vector<T>& a, Comp comp = Comp{}) {
    const std::size_t n = a.size();
    std::vector<T> aux(a);
    long long inv = 0;
    for (std::size_t width = 1; width < n; width *= 2)
        for (std::size_t lo = 0; lo + width < n; lo += 2 * width)
            inv += mergeRuns(a, aux, lo, lo + width, std::min(lo + 2 * width, n), comp);
    return inv;
}

long long inversionsNaive(const std::vector<int>& a) {
    long long c = 0;
    for (std::size_t i = 0; i < a.size(); ++i)
        for (std::size_t j = i + 1; j < a.size(); ++j)
            if (a[i] > a[j]) ++c;
    return c;
}

struct Rec {
    int key;
    char tag;
    bool operator==(const Rec&) const = default;
};

template <class T, class Comp = std::less<T>>
long long run(int which, std::vector<T>& a, Comp comp = Comp{}) {
    return which == 0 ? mergeSort(a, comp) : mergeSortBottomUp(a, comp);
}

int fail(const char* msg) {
    std::cerr << msg << "\n";
    return 1;
}

int main() {
    auto byKey = [](const Rec& x, const Rec& y) { return x.key < y.key; };
    std::vector<std::vector<int>> cases{{}, {1}, {2, 2, 2}, {5, 2, 4, 6, 1, 3}, {8, 7, 6, 5, 4, 3, 2, 1},
                                        {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}};
    std::vector<long long> invs{0, 0, 0, 9, 28, 0};
    for (int w = 0; w < 2; ++w) {
        std::vector<int> t{38, 27, 43, 3, 9, 82, 10};
        if (run(w, t) != 11 || t != std::vector<int>{3, 9, 10, 27, 38, 43, 82}) return fail("trace");
        for (std::size_t k = 0; k < cases.size(); ++k) {
            auto b = cases[k];
            auto expected = cases[k];
            std::sort(expected.begin(), expected.end());
            if (run(w, b) != invs[k] || b != expected) return fail("case");
        }
        std::vector<Rec> recs{{4, 'a'}, {2, 'b'}, {4, 'c'}, {1, 'd'}, {2, 'e'}};
        run(w, recs, byKey);
        if (recs != std::vector<Rec>{{1, 'd'}, {2, 'b'}, {2, 'e'}, {4, 'a'}, {4, 'c'}}) return fail("stable");
    }
    std::mt19937 rng(7);
    for (int t = 0; t < 300; ++t) {
        int n = static_cast<int>(rng() % 41);
        std::vector<Rec> data;
        std::vector<int> keys;
        for (int i = 0; i < n; ++i) {
            data.push_back({static_cast<int>(rng() % 10), static_cast<char>('A' + i)});
            keys.push_back(data.back().key);
        }
        auto expected = data;
        std::stable_sort(expected.begin(), expected.end(), byKey);
        for (int w = 0; w < 2; ++w) {
            auto b = data;
            run(w, b, byKey);
            if (b != expected) return fail("random stable sort");
            auto k = keys;
            if (run(w, k) != inversionsNaive(keys)) return fail("random inversions");
        }
    }
    std::cout << "ok\n";
    return 0;
}
type Cmp<T> = (x: T, y: T) => number;

// Merge sorted a[lo..mid) and a[mid..hi) via aux. Returns the cross inversions.
function merge<T>(a: T[], aux: T[], lo: number, mid: number, hi: number, c: Cmp<T>): number {
  for (let k = lo; k < hi; k++) aux[k] = a[k];
  let i = lo;
  let j = mid;
  let inv = 0;
  for (let k = lo; k < hi; k++) {
    if (i < mid && (j >= hi || c(aux[i], aux[j]) <= 0)) {   // ties go left: stable
      a[k] = aux[i++];
    } else {
      a[k] = aux[j++];
      inv += mid - i;
    }
  }
  return inv;
}

function mergeSort<T>(a: T[], c: Cmp<T>): number {
  const aux = a.slice();
  const sort = (lo: number, hi: number): number => {
    if (hi - lo <= 1) return 0;
    const mid = (lo + hi) >>> 1;
    const inv = sort(lo, mid) + sort(mid, hi);
    if (c(a[mid - 1], a[mid]) <= 0) return inv;             // already in order
    return inv + merge(a, aux, lo, mid, hi, c);
  };
  return sort(0, a.length);
}

function mergeSortBottomUp<T>(a: T[], c: Cmp<T>): number {
  const n = a.length;
  const aux = a.slice();
  let inv = 0;
  for (let width = 1; width < n; width *= 2) {
    for (let lo = 0; lo < n - width; lo += 2 * width) {
      inv += merge(a, aux, lo, lo + width, Math.min(lo + 2 * width, n), c);
    }
  }
  return inv;
}

function inversionsNaive(a: number[]): number {
  let cnt = 0;
  for (let i = 0; i < a.length; i++) for (let j = i + 1; j < a.length; j++) if (a[i] > a[j]) cnt++;
  return cnt;
}

function check(ok: boolean, msg: string): void {
  if (!ok) throw new Error(msg);
}

const num: Cmp<number> = (x, y) => x - y;
type Rec = [number, string];
const byKey: Cmp<Rec> = (x, y) => x[0] - y[0];
const same = (x: unknown, y: unknown): boolean => JSON.stringify(x) === JSON.stringify(y);

for (const sort of [mergeSort, mergeSortBottomUp]) {
  const t = [38, 27, 43, 3, 9, 82, 10];
  check(sort(t, num) === 11 && same(t, [3, 9, 10, 27, 38, 43, 82]), "trace");
  const cases: Array<[number[], number]> = [
    [[], 0], [[1], 0], [[2, 2, 2], 0], [[5, 2, 4, 6, 1, 3], 9], [[8, 7, 6, 5, 4, 3, 2, 1], 28],
    [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 0],
  ];
  for (const [data, inv] of cases) {
    const b = [...data];
    check(sort(b, num) === inv && same(b, [...data].sort(num)), `${sort.name} on ${data}`);
  }
  const recs: Rec[] = [[4, "a"], [2, "b"], [4, "c"], [1, "d"], [2, "e"]];
  sort(recs, byKey);
  check(same(recs, [[1, "d"], [2, "b"], [2, "e"], [4, "a"], [4, "c"]]), "stable");
}

let seed = 7;
const rand = (m: number): number => {
  seed = (seed * 1103515245 + 12345) % 2147483648;
  return seed % m;
};
for (let t = 0; t < 300; t++) {
  const n = rand(41);
  const data: Rec[] = [];
  for (let i = 0; i < n; i++) data.push([rand(10), String.fromCharCode(65 + i)]);
  const keys = data.map((r) => r[0]);
  const expected = [...data].sort(byKey);                    // stable since ES2019
  for (const sort of [mergeSort, mergeSortBottomUp]) {
    const b = [...data];
    sort(b, byKey);
    check(same(b, expected), "random stable sort");
    check(sort([...keys], num) === inversionsNaive(keys), "random inversions");
  }
}
console.log("ok");

Three details the tests pin down. The bottom-up loop runs lo only while lo + width < n, so a trailing block with no partner is skipped rather than "merged" with an empty run. The skip-merge check compares a[mid-1] with a[mid] using the same <= as the merge, so equal boundary elements count as in order (no inversion) — consistent with the counter. And the inversion counter is a 64-bit integer: can have about inversions, which overflows 32 bits.

Variant: insertion sort below a cutoff

# fragment — the hybrid base case, shown for the idea only
CUTOFF = 16

def sort(lo, hi):
    if hi - lo <= CUTOFF:
        insertion_sort_range(a, lo, hi)   # stable, fast on tiny ranges
        return
    mid = (lo + hi) // 2
    sort(lo, mid)
    sort(mid, hi)
    if a[mid - 1] > a[mid]:
        merge(a, aux, lo, mid, hi)

Below a few dozen elements, recursion and copying cost more than insertion sort's quadratic work. Java's legacy merge sort for objects used a cutoff of 7; Timsort uses binary insertion sort to build runs of 32–64. The exact cutoff is an implementation detail found by benchmarking. Insertion sort is stable, so the hybrid stays stable. If you count inversions, have the insertion sort return its shift count — by the theorem in the previous lesson, that is the inversion count of the small range.

Real-world uses

Language standard libraries. Timsort — a natural, run-adaptive merge sort with galloping merges — is the stable sort in CPython (list.sort, sorted), in Java for object arrays and Collections.sort, in V8 (Chrome, Node.js) for Array.prototype.sort, and in Android. Rust's stable slice::sort has always been merge-based (Timsort-like, and since Rust 1.81 a newer design called driftsort). C++ std::stable_sort is a merge sort with a temporary buffer, degrading to when no buffer can be allocated. Perl has used merge sort for sort since 5.8. The reason is the same everywhere: these sorts must be stable and must not have a quadratic worst case on adversarial input.

Linked lists in systems code. The Linux kernel's list_sort (lib/list_sort.c) is a bottom-up merge sort on its intrusive doubly linked lists, written to use extra space and to keep merges balanced for cache behaviour; callers across the kernel, including several filesystems, use it. std::list::sort and std::forward_list::sort in C++ are merge sorts for the same reason — a list has no random access, so quicksort's partitioning and heap sort's indexing do not apply.

External sorting in databases. When a query's ORDER BY, GROUP BY, DISTINCT, index build or merge join needs to sort more rows than fit in its memory budget, the database writes sorted runs to disk and merges them. PostgreSQL reports this in EXPLAIN ANALYZE as Sort Method: external merge Disk: …kB once a sort exceeds work_mem. The merge join itself is a two-way merge of sorted inputs. See How Databases Work, Query Planning & Optimization and, for the full algorithm, Sorting in the Real World.

LSM-tree compaction. Log-structured merge trees — the storage engine of RocksDB, LevelDB, Cassandra and many others — keep data in immutable sorted files (SSTables) and periodically compact them by merging several sorted files into one, dropping overwritten and deleted keys. A compaction is a -way merge. Storage Engines and Build a Key-Value Store show it in context.

Big data frameworks. MapReduce and Hadoop sort each mapper's output into runs, spill them to disk, and merge them on the reducer side ("shuffle and sort"). Spark's sort-based shuffle does the same. The GNU sort command sorts files larger than memory by writing sorted temporary files and merging them, and parallelises with --parallel.

Search and ranking. Merging sorted posting lists is the core of query evaluation in an inverted index: intersecting the document-ID lists for "merge" and "sort" is a merge that outputs only common IDs (Search Engineering). Inversion counts measure disagreement between two rankings — Kendall's tau distance is the number of inversions of one ranking relative to the other — and are computed with exactly the merge-sort counter on this page when is large.

Version control. Three-way merges in Git are not merge sort, but the underlying operation — walk two sorted sequences (of lines, of tree entries sorted by path) in lockstep — is the same two-pointer merge.

Pitfalls & edge cases

  • < instead of <= in the merge. Still sorts, but breaks stability and makes the inversion counter count equal pairs. Test with duplicate keys.
  • Midpoint overflow. (lo + hi) / 2 overflows a 32-bit int when lo + hi exceeds — the bug that sat in Java's Arrays.binarySearch and merge sort for nearly a decade (Joshua Bloch, 2006). Use lo + (hi - lo) / 2 or (lo + hi) >>> 1 in Java.
  • Inversion count overflow. Up to inversions: for that is about , more than a 32-bit integer holds. Use long / long long / Python's ints.
  • Allocating in every call. Creating new lists for every merge (the "slice and concatenate" style) is total allocation and is often 3–10 times slower than one shared buffer. Fine for interviews, not for production.
  • Infinite recursion. Splitting [lo, hi) at mid = (lo + hi) // 2 with the base case hi - lo <= 1 always makes progress. Mixing inclusive and exclusive bounds ([lo, mid] and [mid, hi]) or using a base case of lo == hi with inclusive bounds is the classic source of stack overflows.
  • Bottom-up trailing block. The last block may have no partner, or a partner shorter than width. Clip hi at n and skip blocks with mid >= n.
  • Counting the wrong thing in "count smaller after self". You must sort indices (or (value, index) pairs) so that counts are credited to the original positions; sorting values loses track of whom each count belongs to.
  • Reverse pairs counted during the merge. The condition a[i] > 2·a[j] is not the merge order, so it must be counted with a separate two-pointer pass before merging; folding it into the merge's comparisons gives wrong answers. Also, 2·a[j] overflows 32-bit integers for values near — use 64-bit.
  • Recursion depth in Python. Depth is only , so the default recursion limit is no problem for merge sort itself — but a careless linked-list merge written recursively (merge two lists by recursing on the tails) has depth and will overflow. Merge lists iteratively.

Variations

  • Natural merge sort. Start from the runs already present in the input instead of from single elements. On sorted input: one run, zero merges, comparisons. Timsort is natural merge sort plus a minimum run length, a stack-based merge policy and galloping.
  • Galloping (exponential search) merges. When one run keeps winning, switch from one-at-a-time comparison to exponential search for how many elements in a row it will win, then copy that block. Merging runs of sizes then costs comparisons — much less than when one run is short. Used in Timsort.
  • -way merge. Merge sorted sequences at once with a min-heap holding the current head of each: for total elements. Used in external sorting, LSM compaction and "merge sorted lists" (LeetCode 23). Heaps & Priority Queues covers the heap; a loser tree (tournament tree) does the same with about comparisons per element and is preferred in external sorts.
  • External merge sort. Phase 1: read memory-sized chunks, sort each, write them out as runs. Phase 2: merge runs at a time, where is limited by how many input buffers fit in memory. With bytes of data and bytes of memory, phase 1 produces about runs and phase 2 needs passes; with 100 GB of data and 1 GB of memory, 100 runs merge in a single 100-way pass, so the data is read and written about twice. Replacement selection produces runs of average length on random input, halving the number of runs. Full treatment in Sorting in the Real World.
flowchart LR
    IN["input file<br/>N bytes"] --> R1["run 1: sort M bytes"]
    IN --> R2["run 2: sort M bytes"]
    IN --> RK["run N/M"]
    R1 --> H["k-way merge<br/>(heap or loser tree)"]
    R2 --> H
    RK --> H
    H --> OUT["sorted output file"]
  • Merge sort on linked lists in extra space. Bottom-up: repeatedly walk the list, cutting off two sublists of length width, merging them by relinking, and appending the result to a tail pointer; double width until one pass merges everything. No recursion, no buffer, time, stable. LeetCode 148 below has the code.
  • Parallel merge sort. The two recursive calls are independent, so they can run in parallel; with a parallel merge (split both runs by binary search around a median) the span is or better, and Cole's algorithm (1988) achieves time on processors. Java's Arrays.parallelSort uses a parallel sort-merge on the fork/join pool.
  • Three-way and multiway merge sort. Splitting into parts gives with a heap merge — still , but with fewer passes over memory, which is what matters on disk and helps cache behaviour in memory.
  • Block merge sort (in place, stable). WikiSort and GrailSort: time, extra memory, stable, complicated. Useful when memory is truly constrained.
  • Divide and conquer beyond sorting. "Split, solve halves, combine across the split in linear time" solves closest pair of points, counting inversions, the maximum subarray (as a teaching example), and offline problems via CDQ divide and conquer. The divide-and-conquer lesson in Module 5 generalises the pattern.

Practice ladder

Easy → hard. Descriptions are paraphrased; follow the links for the exact statements.

1. Merge Sorted Array (LeetCode 88) — merge a second sorted array into the first, which has spare room at its end, in place. Teaches the merge run backwards so that nothing is overwritten before it is read.

Hint

Fill from the back: compare the last unread elements of both arrays and write the larger one into the last free slot.

2. Merge Two Sorted Lists (LeetCode 21) — splice two sorted linked lists into one. Teaches the merge by relinking with a dummy head, the building block of list merge sort.

Hint

dummy = tail = ListNode(); while both lists are non-empty, attach the smaller head to tail (ties from the first list for stability) and advance. Attach whatever remains.

3. Sort an Array (LeetCode 912) — sort integers without the built-in sort in . Teaches writing the canonical implementation from memory; note that adversarial tests make naive quicksort time out, while merge sort is safe.

Hint

The page's top-down merge_sort with one auxiliary buffer. Check that [5, 1, 1, 2, 0, 0] and an array of 50,000 equal values both work.

4. Sort List (LeetCode 148) — sort a linked list in time; the follow-up asks for extra space. Teaches bottom-up merge sort on lists.

Hint

Count the length. For width = 1, 2, 4, …: walk the list, cut two sublists of width nodes, merge them, attach to a tail pointer, continue from where you cut. A helper split(head, k) that cuts after k nodes and returns the rest keeps the code short.

Solution
class ListNode:
    def __init__(self, val: int = 0, next: "ListNode | None" = None):
        self.val, self.next = val, next


def split(head, k):
    """Cut the list after k nodes; return the head of the remainder."""
    for _ in range(k - 1):
        if head is None:
            return None
        head = head.next
    if head is None:
        return None
    rest = head.next
    head.next = None
    return rest


def merge_lists(a, b, tail):
    """Merge a and b after tail (stable); return the new tail."""
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    while tail.next:
        tail = tail.next
    return tail


def sort_list(head):
    n, p = 0, head
    while p:
        n, p = n + 1, p.next
    dummy = ListNode(0, head)
    width = 1
    while width < n:
        cur, tail = dummy.next, dummy
        while cur:
            left = cur
            right = split(left, width)
            cur = split(right, width)
            tail = merge_lists(left, right, tail)
        width *= 2
    return dummy.next


def build(xs):
    d = t = ListNode()
    for x in xs:
        t.next = ListNode(x)
        t = t.next
    return d.next


def to_list(h):
    out = []
    while h:
        out.append(h.val)
        h = h.next
    return out


import random
assert to_list(sort_list(build([4, 2, 1, 3]))) == [1, 2, 3, 4]
assert to_list(sort_list(build([-1, 5, 3, 4, 0]))) == [-1, 0, 3, 4, 5]
assert to_list(sort_list(build([]))) == []
rng = random.Random(1)
for _ in range(200):
    xs = [rng.randint(-5, 5) for _ in range(rng.randint(0, 30))]
    assert to_list(sort_list(build(xs))) == sorted(xs)
print("ok")

time, extra space: only a constant number of pointers, no recursion, no buffer. The tail walk at the end of merge_lists is linear in the merged length, so each pass is still .

5. Merge k Sorted Lists (LeetCode 23) — merge sorted linked lists. Teaches the -way merge: a heap of heads () or pairwise merging in rounds, which is bottom-up merge sort over lists.

Hint

Push (node.val, list_index, node) for each non-empty head into a min-heap (the index breaks ties so nodes are never compared). Pop, append, push that node's successor. Or merge lists pairwise: round 1 merges lists 0+1, 2+3, …; each round halves the number of lists.

6. Inversion Count (SPOJ INVCNT) — count inversions in arrays of up to about elements. Teaches the counter on this page, and that the answer needs 64-bit integers.

Hint

merge_sort from the canonical block already returns the count. In C++ or Java make sure the counter is 64-bit.

Solution
def count_inversions(a: list[int]) -> int:
    """Return the inversion count; sorts a copy with merge sort."""
    a = list(a)
    aux = [0] * len(a)

    def sort(lo: int, hi: int) -> int:
        if hi - lo <= 1:
            return 0
        mid = (lo + hi) // 2
        inv = sort(lo, mid) + sort(mid, hi)
        aux[lo:hi] = a[lo:hi]
        i, j = lo, mid
        for k in range(lo, hi):
            if i < mid and (j >= hi or aux[i] <= aux[j]):
                a[k] = aux[i]
                i += 1
            else:
                a[k] = aux[j]
                j += 1
                inv += mid - i
        return inv

    return sort(0, len(a))


assert count_inversions([3, 1, 2]) == 2
assert count_inversions([2, 3, 8, 6, 1]) == 5
assert count_inversions([38, 27, 43, 3, 9, 82, 10]) == 11
assert count_inversions(list(range(1000, 0, -1))) == 1000 * 999 // 2
assert count_inversions([]) == 0
print("ok")

time, space. A Fenwick tree over compressed values (Module 3) gives the same bound and is the other standard answer.

7. Inversion Counting (Codeforces 911D) — a permutation and a sequence of segment reversals; after each reversal, report whether the number of inversions is odd or even. Teaches reasoning about inversion parity instead of recounting.

Hint

Count the initial parity once (, so even works). Reversing a segment of length flips the order of all pairs inside it and leaves every other pair alone, so the parity changes iff is odd.

8. Pair of Topics (Codeforces 1324D) — count pairs with . Teaches rewriting a pair condition as with , after which order no longer matters and sorting plus two pointers (or binary search) counts pairs in .

Hint

With the condition is symmetric in and , so you may sort . For each , count the in sorted order with by binary search. Use 64-bit for the answer.

9. Count of Smaller Numbers After Self (LeetCode 315) — for each element, count the strictly smaller elements to its right. Teaches inversion counting credited per element: sort indices, and when a left element is output, add the number of right elements already output.

Hint

Merge sort an array of indices by value. During a merge, keep moved = how many right-half indices have been output so far. When you output a left-half index p, every right element output before it is smaller and lies to its right: counts[p] += moved. Ties must go left so equal values are not counted.

Solution
def count_smaller(nums: list[int]) -> list[int]:
    n = len(nums)
    counts = [0] * n
    idx = list(range(n))
    aux = [0] * n

    def sort(lo: int, hi: int) -> None:
        if hi - lo <= 1:
            return
        mid = (lo + hi) // 2
        sort(lo, mid)
        sort(mid, hi)
        aux[lo:hi] = idx[lo:hi]
        i, j, moved = lo, mid, 0
        for k in range(lo, hi):
            if i < mid and (j >= hi or nums[aux[i]] <= nums[aux[j]]):
                counts[aux[i]] += moved          # right elements already output are smaller
                idx[k] = aux[i]
                i += 1
            else:
                idx[k] = aux[j]
                j += 1
                moved += 1

    sort(0, n)
    return counts


def brute(nums):
    return [sum(1 for j in range(i + 1, len(nums)) if nums[j] < nums[i]) for i in range(len(nums))]


import random
assert count_smaller([5, 2, 6, 1]) == [2, 1, 1, 0]
assert count_smaller([-1]) == [0]
assert count_smaller([-1, -1]) == [0, 0]
rng = random.Random(3)
for _ in range(300):
    xs = [rng.randint(-5, 5) for _ in range(rng.randint(0, 25))]
    assert count_smaller(xs) == brute(xs)
print("ok")

time, space. Summing the output gives the inversion count — this is the same algorithm, credited per element.

10. Reverse Pairs (LeetCode 493) — count pairs with . Teaches counting a non-merge condition across the halves with a separate two-pointer pass, before merging.

Hint

After both halves are sorted, for each i in the left half advance a pointer j through the right half while a[i] > 2 * a[j]; because the left half is sorted ascending, j never moves back. Add j - mid for each i. Then merge normally.

Solution
def reverse_pairs(nums: list[int]) -> int:
    a = list(nums)
    aux = [0] * len(a)

    def sort(lo: int, hi: int) -> int:
        if hi - lo <= 1:
            return 0
        mid = (lo + hi) // 2
        cnt = sort(lo, mid) + sort(mid, hi)
        j = mid
        for i in range(lo, mid):                 # count first: the condition is not the merge order
            while j < hi and a[i] > 2 * a[j]:
                j += 1
            cnt += j - mid
        aux[lo:hi] = a[lo:hi]                    # then an ordinary merge
        p, q = lo, mid
        for k in range(lo, hi):
            if p < mid and (q >= hi or aux[p] <= aux[q]):
                a[k] = aux[p]
                p += 1
            else:
                a[k] = aux[q]
                q += 1
        return cnt

    return sort(0, len(a))


def brute(nums):
    n = len(nums)
    return sum(1 for i in range(n) for j in range(i + 1, n) if nums[i] > 2 * nums[j])


import random
assert reverse_pairs([1, 3, 2, 3, 1]) == 2
assert reverse_pairs([2, 4, 3, 5, 1]) == 3
assert reverse_pairs([2147483647] * 5) == 0
rng = random.Random(5)
for _ in range(300):
    xs = [rng.randint(-20, 20) for _ in range(rng.randint(0, 25))]
    assert reverse_pairs(xs) == brute(xs)
print("ok")

: the counting pass is linear per merge because j only moves forward. Negative numbers are fine — the left half is still sorted, so thresholds are still monotone. In Java or C++ compute 2L * a[j] to avoid overflow.

11. Count of Range Sum (LeetCode 327) — count subarrays whose sum lies in . Teaches reducing to pairs of prefix sums -style conditions — count pairs with — and counting them across merge-sort halves with two monotone pointers.

Hint

Build prefix sums . For each left-half (sorted), the valid right-half form a contiguous window in the sorted right half; two pointers lo_ptr and hi_ptr only move forward as increases. Add hi_ptr - lo_ptr, then merge.

Solution
def count_range_sum(nums: list[int], lower: int, upper: int) -> int:
    p = [0]
    for x in nums:
        p.append(p[-1] + x)
    aux = [0] * len(p)

    def sort(lo: int, hi: int) -> int:
        if hi - lo <= 1:
            return 0
        mid = (lo + hi) // 2
        cnt = sort(lo, mid) + sort(mid, hi)
        a_ptr = b_ptr = mid
        for i in range(lo, mid):
            while a_ptr < hi and p[a_ptr] - p[i] < lower:
                a_ptr += 1
            while b_ptr < hi and p[b_ptr] - p[i] <= upper:
                b_ptr += 1
            cnt += b_ptr - a_ptr
        p[lo:hi] = sorted(p[lo:hi])              # merge (sorted() on two runs is Timsort: linear here)
        return cnt

    return sort(0, len(p))


def brute(nums, lower, upper):
    n = len(nums)
    return sum(1 for i in range(n) for j in range(i, n) if lower <= sum(nums[i:j + 1]) <= upper)


import random
assert count_range_sum([-2, 5, -1], -2, 2) == 3
assert count_range_sum([0], 0, 0) == 1
rng = random.Random(9)
for _ in range(200):
    xs = [rng.randint(-6, 6) for _ in range(rng.randint(1, 15))]
    lo = rng.randint(-5, 3)
    up = lo + rng.randint(0, 5)
    assert count_range_sum(xs, lo, up) == brute(xs, lo, up)
print("ok")

time. The sorted() call on a range made of two sorted runs is a shortcut: Timsort detects the two runs and merges them in linear time, so the bound holds; in other languages write the merge.

12. String Reversal (Codeforces 1430E) — the minimum number of adjacent swaps that turn a string into its reverse. Teaches reducing to inversions: match the -th occurrence of each letter in the reversed string to the -th occurrence in the original, build the resulting permutation, count its inversions.

Hint

For each letter keep a queue of its positions in the original string. Walk the reversed string; for each letter pop the earliest unused original position — matching occurrences in order never creates an unnecessary inversion. The answer is the inversion count of the sequence of popped positions; use 64-bit.

13. Create Sorted Array through Instructions (LeetCode 1649) — insert numbers one by one; each insertion costs the smaller of (elements strictly less) and (elements strictly greater) already present; total cost modulo . Teaches computing "smaller before" and "greater before" for every element — two inversion-style counts — with merge sort or a Fenwick tree.

Hint

For each position , "less before " is a count of smaller elements to the left — the mirror image of LeetCode 315. "Greater before " = − (less or equal before ). Compute both with merge sort on indices (or a Fenwick tree over values, Module 3), then sum the minimums.

14. Number of Pairs Satisfying Inequality (LeetCode 2426) — count pairs with . Teaches the general recipe: move everything indexed by to one side and by to the other ( with ), then count across merge-sort halves with one monotone pointer.

Hint

After sorting both halves of : for each right-half , the valid left-half are those , a prefix of the sorted left half whose length only grows as grows. Count with a pointer, then merge.

Common mistakes & interview follow-ups

"Merge sort or quicksort?" Merge sort: stable, guaranteed , sequential access, natural for linked lists and external data, fewer comparisons; costs extra memory and more data movement. Quicksort: in place, usually faster on arrays of primitives because it moves less data, but unstable and in the worst case unless guarded (introsort). Libraries use quicksort variants for primitives, where stability is meaningless, and merge-based Timsort for objects.

"Can you make merge sort use extra space?" On a linked list, yes — bottom-up relinking. On an array, only with in-place merging: with rotations, or with block merge sort at a large constant. Saying "allocate one buffer of and copy only the smaller run" is the practical answer.

"What is the recursion depth?" , independent of the input. (Quicksort's depth can be without care.)

"Your inversion count is wrong for duplicates." Usually < instead of <= in the merge, which counts equal pairs as inversions.

"The data is 100 GB and you have 1 GB of RAM." External merge sort: produce 100 sorted runs of 1 GB, then one 100-way merge with a heap or loser tree, reading each run through its own buffer. Two passes over the data. Mention that sequential I/O dominates, so large buffers and fewer passes matter more than CPU.

"What if the input is a stream and you need the sorted output incrementally?" You cannot output the minimum before seeing all elements, so a full sort needs all data. If the stream consists of several sorted streams, a -way merge outputs incrementally.

"Count pairs with / / …" Same template as reverse pairs: sort halves, count across with a monotone pointer, merge. The condition must be monotone in both and for the pointer to work.

"Why not count inversions with a Fenwick tree instead?" You can: compress values, sweep left to right, query "how many seen so far are greater". Same , often simpler for online variants. Merge sort needs no extra structure and no coordinate compression, and it naturally handles the cross-half conditions (reverse pairs, range sums) that are awkward for a Fenwick tree.

Quick quiz

1. How many comparisons does merging [1, 2, 3] with [4, 5, 6] take? Merging [1, 3, 5] with [2, 4, 6]?

Answer

3 and 5. In the first, 1, 2 and 3 each beat 4, after which the left run is empty and 4, 5, 6 are copied without comparisons: . In the second the runs interleave to the end: .

2. Count the inversions of [2, 4, 1, 3, 5] and say in which merge of a top-down merge sort each is found.

Answer

Three: , , . Top-down splits into [2, 4] and [1, 3, 5]; [2, 4] has none; [1, 3, 5] splits into [1] and [3, 5] and has none. The final merge of [2, 4] with [1, 3, 5] outputs 1 while 2 and 4 wait (+2) and 3 while 4 waits (+1): all 3 are cross inversions found in the last merge.

3. Why is case 2 of the Master theorem, and what changes if the merge cost instead?

Answer

and matches it, so . With (and the regularity condition for ) it is case 3: — the root's work dominates.

4. You change <= to < in the merge. Does the output stay sorted? What else changes?

Answer

It stays sorted, but among equal keys the right half's element is output first, so the sort becomes unstable, and the inversion counter adds mid - i for equal pairs, overcounting by the number of equal pairs that straddle a split.

5. Bottom-up merge sort is run on a linked list of 1,000 nodes. How many passes, and how much extra memory?

Answer

passes (widths ), and extra memory — a handful of pointers. Each pass is , so total.

Further reading / sources

  • Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed. (1998) — §5.2.4 (sorting by merging, exact counts), §5.3.1 (minimum-comparison sorting and ), §5.4 (external sorting, replacement selection, loser trees).
  • Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), 4th ed. — §2.3 (merge sort and its analysis), §4.3–4.5 (recursion trees and the master theorem), Problem 2-4 (inversions).
  • Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed. — §2.2 (mergesort, top-down and bottom-up, the cutoff and skip-merge improvements).
  • Jon Kleinberg and Éva Tardos, Algorithm Design (2005) — §5.3 (counting inversions, with the ranking motivation).
  • Philippe Flajolet and Mordecai Golin, "Mellin Transforms and Asymptotics: The Mergesort Recurrence", Acta Informatica 31, 1994 — the exact average and the oscillating linear term.
  • Bing-Chao Huang and Michael A. Langston, "Practical In-Place Merging", Communications of the ACM 31(3), 1988.
  • Tim Peters, listsort.txt — Timsort's runs, galloping and merge policy.
  • Joshua Bloch, "Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken", Google Research Blog, 2006 — the midpoint overflow.
  • Linux kernel source, lib/list_sort.c — a production bottom-up linked-list merge sort.
  • cppreference: std::stable_sort, std::inplace_merge — complexity with and without a buffer.
  • PostgreSQL documentation, Using EXPLAIN — reading Sort Method: external merge.

Lessons: previous — Elementary Sorts & Stability · next — Quick Sort, Partition Schemes & Introsort · module — Searching & Sorting · course — DSA: Zero to Mastery.

Related Archon pages: Two Pointers · Linked Lists · Heaps & Priority Queues · Recursion & Mathematical Induction · Complexity Analysis · Sorting in the Real World · Storage Engines · Sorting & Searching (overview).