Merge Sort Explorer

Watch the recursion tree unfold — the array splits into colored halves down to single elements, then each value visibly flies back up as sorted runs merge into one.

This interactive merge sort visualization turns the divide-and-conquer algorithm into a recursion tree you can watch unfold. The full array sits at the top; it splits into a blue left half and a violet right half, and those halves keep splitting downward until every element stands alone. Then the animation runs in reverse: sorted runs merge back upward, two at a time, until the whole array is in order.

Merge sort's cost is $T(n) = 2T(n/2) + \Theta(n) = \Theta(n \log n)$, and this holds in the best, average, and worst case — the recursion tree's shape depends only on $n$, never on how shuffled the input is. During each merge you can watch the two runs' front values get compared and the smaller one fly up into the parent's next open slot, which is exactly why the algorithm is stable: equal keys keep their original order.

Step through it one comparison at a time, or jump by whole merges or recursion levels. Try the presets — random, reversed, nearly sorted, few unique, and a power-of-two size — to see how the tree stays balanced regardless. It's the clearest way to grasp why splitting a problem in half and combining the answers gives $n \log n$ performance, and how merge sort differs from in-place sorts like bubble sort by using a temporary buffer for each merge.