Merge Sort

Divide & Conquer Sorting

1:00

How merge sort's divide-and-conquer strategy delivers guaranteed O(n log n) performance — stable, predictable, and powering real-world library sorts.

By the end, you can

Explain the divide-and-conquer structure of merge sort and identify its three phases.
Trace the recursion tree for a small array and state its depth in terms of n.
Simulate the two-pointer merge of two sorted runs and produce the correct output order.
State the time complexity (O(n log n), all cases) and justify it from the cost model.
Identify why merge sort is not in-place and what the O(n) buffer is used for.
Explain what makes merge sort stable and which line of code provides that guarantee.
Compare merge sort, quicksort, and heapsort on time, space, and stability.
Describe where merge sort is applied in practice (external sorting, Timsort, linked lists).

Up next in Searching & Sorting