Break it down. Build it back, sorted.
Divide a big problem into small ones. Solve the small ones. Combine their answers.
Down to single values. Back to one array.
Parent groups sit above their two halves. Small # labels show original positions, so equal values remain distinguishable. Scroll to explore larger trees.
Compare the fronts. Take the smaller.
This workbench becomes active when two sorted groups are ready to merge.
LEFT GROUP
RIGHT GROUP
SORTED OUTPUT →
Small answers solve the bigger problem.
The split halves the problem size. During a merge, both inputs are already sorted, so only their front values need comparing. Each chosen value is written once into that merge’s output.
O(n log n) time: about log₂ n levels, with O(n) merging work per level.
O(n) auxiliary space: a standard merge sort uses a temporary buffer. This teaching view also retains the tree and playback history.
Stable: choosing the left value on ties preserves the original order of equal values.
For clarity, this animation shows all divisions first, then merges bottom-up. A recursive implementation interleaves splitting and merging as each call returns.