Merge Sort
Medium+90 XPDivide the array in half, sort each half, then merge them. O(n log n).
No visualization loaded.
Watch
—
Press Run to begin.
Merge sort wins by dividing the problem. Split the array in half, then split those halves, and keep splitting until every piece is a single element (which is already 'sorted'). Then merge pieces back together two at a time, always keeping each merged piece in order. Build up from tiny sorted pieces to one fully sorted whole. It's the first 'divide and conquer' algorithm you'll meet.
▸What does 'divide and conquer' mean?
Break a big problem into smaller copies of the same problem, solve those, then combine the answers. Here: sorting a big array = sorting its two halves (smaller sort problems) + merging the results. A problem that calls smaller versions of itself is recursion — the same idea you'll see in the factorial lesson.
▸How do you 'merge' two sorted halves?
Put a finger on the front of each half and repeatedly take the smaller of the two, advancing that finger. Because both halves are already sorted, the smallest unused value is always at one of the two fingers — so one clean sweep merges them in order. (Yes, that's the two-pointers idea again.)
▸Why is it O(n log n), and why is that so much better than O(n²)?
You can only halve n items about log n times (the number of split levels), and each level does about n work to merge — so n × log n total. For a million items, O(n²) is ~a trillion operations; O(n log n) is ~20 million. That enormous gap is why real-world sorting uses O(n log n) methods, not bubble/insertion.
▸What's the catch?
Memory. Merging needs a temporary copy to build the combined piece, so merge sort uses O(n) extra space — unlike the in-place bubble/insertion sorts. It trades some memory for a big speed win, which is usually a great deal.
How the work grows
O(n log n) is good — the practical sorting speed. About log n levels of splitting, each doing n work to merge — n×log n. The curve sits far below O(n²): on a million items that's ~20 million steps vs ~a trillion. The price is O(n) extra memory for merging.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.