merge sort as divide and conquer

Merge sort is the textbook example of divide and conquer, and the everyday picture is exactly the box-of-forms story: to sort a pile, split it in half, sort each half the same way, then merge the two sorted halves into one. It keeps splitting until each piece is a single card — which is trivially sorted — and then does all its real work on the way back up, merging small sorted runs into larger ones.

Step by step on [5,2,4,1]: DIVIDE into [5,2] and [4,1]. Recurse: [5,2] divides into [5] and [2], which merge to [2,5]; [4,1] divides into [4] and [1], which merge to [1,4]. COMBINE: merge [2,5] and [1,4] with the two-finger scan — take 1, take 2, take 4, take 5 — giving [1,2,4,5]. The merge of two sorted lists of total length n is a single linear pass, so combine costs O(n), and the recurrence is T(n) = 2 T(n/2) + O(n). You can prove correctness by induction on the recursive calls: a one-element array is sorted (base case), and if both recursive calls return correctly sorted halves, the merge step provably outputs them in sorted order, so the whole result is sorted.

Solving T(n) = 2 T(n/2) + O(n) gives O(n log n) in the worst, best, and average case — merge sort never degrades to O(n^2), which is its big advantage over plain quicksort. It is also stable (equal keys keep their original order) and merges sequentially, which makes it the algorithm of choice for sorting data on disk or linked lists. The price is space: the standard merge needs an O(n) auxiliary array, so it is not in-place. That memory cost is the usual reason quicksort is preferred for in-memory arrays despite quicksort's worse worst case.