Divide & Conquer and Merge Sort

Divide and conquer means: split the problem in half, solve each half recursively, then combine the two answers. The cleverness always lives in the combine step. Merge sort is the cleanest example — the combine step zips two already-sorted halves together in one linear pass.

This animation shows merge sort as a tournament bracket. The array splits level by level until every element stands alone (a single element is trivially sorted), then sorted mini-rows zipper back together card by card, level by level, until the full array is rebuilt in order.

What to watch for:

• The depth of the bracket. Halving n repeatedly reaches size 1 in about log n levels — for 16 elements, just 4 levels. The full recursion tree stays visible so you can count them.
• The work per level. Every level touches all n elements exactly once during its merges. About log n levels, times n work per level, is where O(n log n) comes from — read it straight off the picture.
• The zipper move. Each merge only ever compares the two front cards of the two sorted halves. That's why combining is cheap: sortedness lets you make each decision with one comparison.

The same split-solve-combine skeleton drives quickselect, counting inversions, and building trees from traversals — only the combine step changes.