Intermediate · INTERACTIVE LESSON
Merge sort
Split into halves, then merge sorted runs while preserving equal-value order.
The interactive player is loading. If it does not appear, you can still read the explanation below.
THE IDEA BEHIND THE STEPS
How it works
Top-down merge sort splits half-open ranges [start, end) until each has at most one value. After both children return, compare their front values and write the smaller into an auxiliary buffer. Choose the left item on equality: original-index labels show why the sort is stable. Copy the merged buffer back before returning to the parent.
For n ≥ 2, best, average and worst time are Θ(n log n) for this standard implementation, which always merges even already ordered halves. Empty and single-value inputs take Θ(1) algorithm work and zero comparisons or writes. The algorithm uses O(n) auxiliary buffer space and O(log n) recursion stack space; playback snapshots consume additional memory.
Comparisons count only key-to-key tests when both halves have remaining items. Writes count each item placed in the buffer and each item copied back; input initialization and trace snapshots are excluded. Recursion depth is zero at the root. The main array remains unchanged while a buffer is built; copy-back is shown as a batch with one write counted per item. Animation duration is not runtime. Reduced motion retains every state without movement.