In bottom-up merge sort with pass widths 1, 2, 4, what breaks when the final run is shorter than the width?

## The shape of the bottom-up algorithm The recursive formulation descends to single elements and merges on the way back up. The bottom-up formulation skips the descent and starts where the recursion would have bottomed out: every single element is already a sorted run of length 1. It then makes explicit passes. - Pass 1 (`width = 1`): merge runs of 1 into runs of 2. - Pass 2 (`width = 2`): merge runs of 2 into runs of 4. - Pass 3 (`width = 4`): merge runs of 4 into runs of 8. - … until `width >= n`, at which point one sorted run covers the array. That is `ceil(log2 n)` passes, each touching all n elements — the same `Theta(n log n)` total, arrived at by iterating the levels of the recursion tree rather than recursing through them. ## The boundary problem Inside a pass, blocks begin at `lo = 0, 2*width, 4*width, ...`. The block's left run is `a[lo .. lo+width-1]` and its right run is `a[lo+width .. lo+2*width-1]`. Both of those upper bounds can exceed the array when the array length is not a multiple of `2*width` — which, since n is rarely a power of two, happens in almost every pass. There are three cases for the last block of a pass: 1. **Full block.** `lo + 2*width <= n`: both runs are complete, ordinary merge. 2. **Partial right run.** `lo + width < n < lo + 2*width`: the left run is full, the right run is short. The merge must stop at n rather than at `lo + 2*width`. 3. **No right run at all.** `lo + width >= n`: the tail is shorter than a single width. There is nothing to merge it with in this pass; it is already sorted and simply waits for a later, wider pass to absorb it. Clamping both indices with `min(..., n)` handles all three uniformly. In case 3, `mid` and `hi` both become n, so the merge sees an empty right run and copies the left run through unchanged — correct, if slightly wasteful. In case 2 the merge simply ends early. The two failure modes are symmetric and both common: - **Forget the clamps** and the merge indexes past the end of the array, or — worse, if the surrounding buffer happens to be large enough — reads stale slots and produces a silently wrong result. - **Skip the short block** on the theory that "there is nothing to merge" and the tail is never folded into the sorted prefix, so the array ends up sorted except for a wrong-looking suffix. This bug is invisible whenever the test data has a power-of-two length, which is exactly the length a hand-written test tends to use. ## Worked example: n = 10, pass width 4 Blocks begin at 0 and 8. The first block merges `a[0..3]` with `a[4..7]` — a full block. The second begins at `lo = 8`: `mid = min(12, 10) = 10` and `hi = min(16, 10) = 10`, so the left run is `a[8..9]` and the right run is empty. Those two elements were already sorted together by the previous pass, and they stay put until the `width = 8` pass merges `a[0..7]` with `a[8..9]`. The whole array is sorted after that final, lopsided merge. ## What the bottom-up form buys and costs **Buys:** - **No recursion.** The `O(log n)` stack disappears, which matters under a hard stack limit, in a constrained batch environment, or wherever deep recursion is discouraged. - **Explicit levels.** Each pass is an independent sweep, which makes the level-by-level cost argument visible and makes per-pass parallelism or instrumentation straightforward. - **Natural ping-pong.** Alternating source and destination arrays per pass falls out of the structure, removing the copy-back. **Costs:** - **Weaker locality.** The recursive form descends depth-first, so a subproblem small enough to sit in cache is finished completely before moving on. The iterative form sweeps the whole array at each width, revisiting distant memory sooner. - **Awkward small-run cutoff.** The standard optimisation of sorting tiny runs with a simple insertion-style method fits the recursive form neatly at the base case; bottom-up needs a separate initial pass to build runs of, say, 32 before the doubling starts. ## What does not change The auxiliary buffer is still linear — iterating instead of recursing removes the stack, not the merge buffer. The bound is still `Theta(n log n)` on every input. Stability still holds, provided merges take from the left run on ties and blocks are paired left-to-right so the left run always holds the earlier elements. Anyone claiming the iterative version is asymptotically different, buffer-free, or unstable has confused the removal of the call stack with a change to the algorithm.