Merge Sort Cascade Screensaver
The Merge Sort Cascade screensaver shows a real live merge sort as its actual recursion tree, splitting a shuffled array into halves and merging them back in sorted order. It is free, runs in your browser, and ESC exits.
Live preview
Press ESC to leave fullscreen. Settings are saved in your browser only.
How the Merge Sort Cascade screensaver works
The saver shuffles a real array, then recursively splits it in half over and over, drawing every level of the real recursion tree.
Once a segment is down to one element, the real algorithm begins merging pairs of sorted segments back together in order.
Each merge step is drawn live, comparing the fronts of two segments and taking the smaller one, exactly as real merge sort does.
Once the whole array merges back into one fully sorted segment, it holds briefly, then a fresh shuffle and cascade begins.
Divide, conquer and guaranteed n log n
Merge sort is a textbook case of divide and conquer, and a routine for merging two sorted sequences was written by John von Neumann in 1945 as part of what is now regarded as the first version of the algorithm. It splits a list in half, sorts each half by applying itself again, and then merges the two sorted halves into one. Because a list of one element is already sorted, the recursion has a natural stopping point.
The work is in the merge. Given two sorted lists, you repeatedly compare their front elements and take the smaller, which needs only one pass. Each level of the recursion tree does about n units of merging in total, and there are roughly log base two of n levels, giving a running time proportional to n log n in the best, average and worst cases alike. Unlike quicksort, there is no unlucky input that makes it slow.
The cost is memory: the usual implementation needs an auxiliary array about as large as the input. It is also stable, meaning that equal items keep their original order. Variants build on it: Timsort, the algorithm behind Python’s built-in sorted() and list.sort(), is an adaptive hybrid of merge sort and insertion sort that exploits runs of already ordered data.
A worked example
Two small sorted segments of three elements each merge into one sorted segment of six, visibly interleaving their elements in the real comparison order merge sort actually uses.
Settings & tips
- Accent recolours the active merge segment.
- This is a real, correct, unmodified merge sort implementation.
- A fresh shuffle starts automatically once the cascade completes.
Frequently asked questions
- Is this a real merge sort?
- Yes — a real, correct recursive merge sort, with every split and merge drawn as it actually happens.
- Why show the recursion tree?
- It makes the real divide-and-conquer structure visible, not just the final sorted result.
- Is a key needed?
- No — it is a pure local computation.
- Is it free?
- Yes — free, no download, in your browser.
- Why is merge sort always n log n?
- The list is always halved, giving about log n levels, and each level merges a total of n items, regardless of the original order.
- What does stable mean?
- A stable sort keeps items with equal keys in the order they started. Merge sort does this as long as ties are taken from the left half first.
- When is merge sort a poor choice?
- When memory is tight, since it needs extra space for merging, or for small arrays where simpler methods have less overhead.