Merge sort: the idea
Prerequisites: Arrays, recursion, and merging two sorted sequences.
Recursion means solving a smaller instance of the same problem. Merge sort splits a range into two halves, recursively sorts each half, then merges them. The merge copies both halves into temporary storage and repeatedly writes the smaller front item back into the array. If the values are equal, it takes the left item first to preserve original order.
Try it on the same input
Watch the active range shrink to single items, then grow as sorted halves merge. The buffer shows the two copied halves and marks consumed items. During a write, the main array can temporarily repeat an identity; unwritten items remain safe in the buffer.
Time, memory, and stability
n is the number of input items. Best, average, and worst O(n log n) for this version. O(n) auxiliary space, including temporary merge storage; recursion depth O(log n).
A stable sort preserves the original order of items whose values are equal. This implementation is stable. Identity labels record each item’s initial position. An unstable algorithm can preserve equal-item order on a particular input; it makes no guarantee for all inputs.
These bounds describe the sorting algorithm itself. The visualization saves a copy of the array at every operation for reversible playback, so recording uses additional time and memory. Its input size is capped at 24 items.
When to use it—and what to watch
Predictable performance and stability come with extra storage. The playback records each operation, so its memory use exceeds the algorithm’s working memory.
Reading the display
Comparisons count tests between item values. A swap writes two array positions; a merge write updates one. The counters exclude copying merge buffers, index tests, and playback work, so they are teaching measurements rather than elapsed-time benchmarks. Green marks final positions; a highlighted range indicates current work. For recursive algorithms, depth counts the active call levels.
Continue exploring
- Bubble sort — Compare neighbors and let large values travel to the right.
- Selection sort — Find the smallest remaining item and place it in the next slot.
- Insertion sort — Grow a sorted prefix by moving each new item into place.
- Quicksort — Partition around a pivot, then sort the ranges on either side.