= FIFO natural merge sort workspace bound
{c}
{title2=$\Theta(n\log n)$}
Repeatedly removing the first two <maximal initial runs> and appending their sorted merge uses $\Theta(n\log n)$ total fresh output cells in the worst case if obsolete cells are never reused. Group merges into rounds that consume the runs present at the start: the run count is at least halved up to rounding, and each round writes at most $2n$ values. A tight-order family consists of $2^h$ copies of $[0,1]$: run boundaries never coalesce and every merging level writes $n=2^{h+1}$ entries. Its final append-only endpoint is exactly $n\log_2 n$.
Back to article page
