Merge Sort — Divide, Conquer, Combine

Split the array in half, recursively sort each half, then merge the two sorted halves with a two-pointer scan. Total cost T(n) = 2T(n/2) + O(n) = O(n log n), stable, O(n) extra space.

step 0

Recursion tree (divide → merge)

left run right run merged output sorted segment

Current merge (two-pointer)

Press Step to begin merging.
left L
right R
output
Compare the two front elements; copy the smaller (take from the left on ties → stable).
Press Step to begin. We recursively split the array down to single elements, then merge sorted runs back up. Each merge is a linear two-pointer scan.
Self-contained visualization. The merge uses L[i] <= R[j] (take the left run on ties), which makes merge sort stable. There are log₂(n) levels of merges, each doing O(n) total work — that is the O(n log n) bound. See junior.md and professional.md for the proof that the merge is correct and stable.