Merge Sort Theory

Recursive halving builds a perfectly balanced recursion tree; linear merges at each level aggregate into the classic deterministic O(n log n) bound while preserving stability.

Recurrence

T(n) = 2T(n/2) + n. Master Theorem (a=2, b=2, f(n)=n) ⇒ T(n)=Θ(n log n). Every level combines n elements; there are log n levels from halving.

level work: n × log n → n log n

Structure

Perfectly balanced binary recursion
Linear merge cost per level
Stable ordering via left-first tie resolution
Auxiliary array reused per merge pass

Bottom-up variant iteratively merges runs of size 1,2,4,... eliminating recursion depth.

Pseudocode

1function mergeSort(arr):
2  if length(arr) <= 1: return arr
3  mid = length(arr) // 2
4  left = mergeSort(arr[0:mid])
5  right = mergeSort(arr[mid:])
6  return merge(left, right)

Stability arises because equal elements from left half are consumed before right half in typical two-pointer merge.

Properties & Practical Notes

Predictable performance (no pathologies)
Parallelizable at upper tree levels
Good cache locality with blocked merges
External sorting foundation (k-way merge)

Cutoff optimization: Switch to insertion sort below a small threshold (like 8–16) to reduce overhead.

Memory reuse: Allocate one auxiliary buffer and alternate source/destination roles per level to halve copying.

Run Simulation Quick Sort