Bottom-up mergesort

Cost and properties

time	Θ(n log n)
passes	⌈lg n⌉
recursion	none
stable	yes

Reference: Sedgewick & Wayne, §2.2.

Bottom-up mergesort in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

def sort(a):
    n = len(a)
    aux = list(a)
    width = 1
    while width < n:                      # 1, 2, 4, 8, ... subarray size
        for lo in range(0, n - width, 2 * width):
            merge(a, aux, lo, lo + width - 1, min(lo + 2 * width - 1, n - 1))
        width *= 2
    return a

def merge(a, aux, lo, mid, hi):
    aux[lo:hi + 1] = a[lo:hi + 1]
    i, j = lo, mid + 1
    for k in range(lo, hi + 1):
        if i > mid:
            a[k] = aux[j]; j += 1
        elif j > hi:
            a[k] = aux[i]; i += 1
        elif aux[j] < aux[i]:
            a[k] = aux[j]; j += 1
        else:
            a[k] = aux[i]; i += 1

Why it works

Same merges, different order

Top-down mergesort merges small ranges first because the recursion bottoms out; bottom-up simply starts there. The set of merges performed is essentially the same, and so is the cost — but there is no call stack, no recursion depth, and the loop structure is trivial to reason about.

The two boundary details

• range(0, n - width, 2*width) stops early on purpose: if fewer than width keys remain after lo, there is no second half to merge, so that piece is skipped and carried into the next pass.
• min(lo + 2*width - 1, n - 1) clamps the last range when n is not a power of two.

Get either wrong and the sort quietly loses keys at the tail. Run a 10-key input and watch the ragged final merge of each pass.

Why it matters in practice

This is the mergesort of choice for linked lists (no random access needed, and it can run in constant extra space) and for hardware or embedded settings where recursion is unwelcome. It is also the shape of the classic external sort: merge sorted runs from tape/disk, doubling the run length each pass.

What to try in the animation

Try a length that is not a power of two (10 is not): the last merge of each pass is short, which is what min(...) and n - width are for.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

• random — 7 10 5 3 8 4 2 9 6 1
• MERGESORTEXAMPLE — M E R G E S O R T E X A M P L E
• already sorted — 1 2 3 4 5 6 7 8 9 10
• reverse sorted — 10 9 8 7 6 5 4 3 2 1
• all equal — 5 5 5 5 5 5 5 5
• few distinct — 2 1 3 1 2 3 1 2 3 1

Open Bottom-up mergesort in the player →

The rest of Mergesort

• Mergesort (top-down) Sort each half, then merge. The merge is the only real work, and it is linear — which is…