Merge sort and external sorting

Merge sort splits data, sorts both halves, then merges with two pointers. Its invariant is that the chosen prefix is sorted and the next minimum is at one of the two remaining heads. Choosing the left item on equality preserves stability.

Balanced splitting gives Θ(n log n) time for sorted, reversed and duplicate-heavy inputs. Standard array variants need buffers. Python slices copy sublists, so allocation differs from an index-based implementation. Linked-list variants can relink nodes, but recursive stack space still counts.

External merge sort handles data exceeding RAM: sort memory-sized runs, write them, then perform a buffered k-way merge. A priority queue holds run heads; block I/O and buffer counts become central costs.

A sorting-selection atlas

Algorithm	Worst-case time	Typical auxiliary space	Stable?
Insertion	Θ(n²)	O(1), in-place model	Yes with strict comparisons
Merge	Θ(n log n)	O(n), standard array merge	Yes if ties favour the left
Quick	Θ(n²)	Worst-case O(n) stack	Not standard swapping versions
Heap	Θ(n log n)	O(1), iterative in-place	No
Counting	Θ(n+k)	O(n+k), stable output	With a suitable implementation
Radix	Θ(d(n+k))	Depends on digit sorting	If every pass is stable

Expected Θ(n log n) quicksort does not erase its quadratic worst case. Linked-list merging can relink nodes with different space trade-offs. Python slicing allocates; do not transfer an abstract in-place claim to this code.

Merge invariant: the output prefix is sorted and contains each consumed input element exactly once. Choosing the smaller head preserves it. Choosing the left on equal keys preserves stability. The remaining suffix is already sorted and can be appended.

Foundation: Trace merging [2,5,8] and [1,5,7]. Intermediate: Test stability with (key, originalIndex) pairs. Advanced: Design a 100 GB external sort: runs, fan-in, buffers and disk passes. Use an I/O model, not only RAM complexity.

def merge_sort(a):
    if len(a) < 2: return list(a)
    m = len(a)//2
    left, right = merge_sort(a[:m]), merge_sort(a[m:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]: out.append(left[i]); i += 1
        else: out.append(right[j]); j += 1
    return out + left[i:] + right[j:]
assert merge_sort([5,1,4,2]) == [1,2,4,5]