Merge sort
Divide in half, sort each half, merge — and solve the recurrence for O(n log n). · 8 min read
Merge sort is the textbook divide and conquer sort. Split the array in half, sort each half (recursively, the same way), then merge the two sorted halves into one. The merge is the clever part: with both halves sorted, you walk them with two pointers and always take the smaller front element.
Interactive visualization: Merge sort — split then merge — step through it frame by frame on this page.
Deriving the cost
Let T(n) be the work to sort n items. Each call does two half-sized sorts plus a linear merge. That gives a recurrence:
T(n) = 2·T(n/2) + O(n)— Two half-problems, plus an O(n) merge.the splitting forms a tree of depth log₂ n— Halving from n down to 1.each level merges O(n) elements total— Every level touches all n items once.total = (work per level) × (levels) = n × log n— Multiply them.
Result: O(n log n)
Interactive visualization: n work per level × log n levels — step through it frame by frame on this page.
Practice: Merge Two Sorted Arrays (Easy) — The merge step at the heart of merge sort.
Practice: Count Inversions (Hard) — How far is the array from sorted? Count out-of-order pairs in O(n log n).