Merge Sort

Merge sort and quick sort both run in `O(n log n)`, and once you write down their recurrences (`T(n) = 2T(n/2) + O(n)` and its expected-case sibling) the same `n log n` falls out of both. That is not a coincidence: divide and conquer is a paradigm with a precise mathematical signature, and the Master Theorem reads it directly off the recurrence. **Divide and Conquer (Intro)** introduces the three-step pattern (divide, conquer, combine) and the recurrence-relation toolkit that comes with it. You will analyze merge sort and quick sort as canonical D&C algorithms, look at binary search through the same lens, walk through the divide-and-conquer maximum subarray algorithm, and meet the closest-pair-of-points problem in 1D. Along the way the lesson formalizes the Master Theorem template `T(n) = aT(n/b) + f(n)` and shows you how to read time complexity off it without solving the recurrence by hand. It also draws the line between D&C (independent subproblems) and DP (overlapping subproblems) so you can spot which paradigm fits. In **Recursion Fundamentals**, you saw recursion as one frame calling another. D&C is the case where a frame makes _multiple_ recursive calls and combines their results. Next, **Matrix Algorithms** turns to two-dimensional arrays.

When you call `arr.sort()` in Python or JavaScript, you are running Timsort, an industrial-strength hybrid that switches between merge sort for long runs and insertion sort for short ones. Sorting a billion elements in seconds is possible only because someone, decades ago, broke the `O(n^2)` ceiling that bubble sort, selection sort, and insertion sort all sit beneath. This lesson is where you learn how. **Sorting (Advanced)** covers the comparison-based `O(n log n)` algorithms (merge sort, quick sort, heap sort) and the non-comparison sorts (counting sort, radix sort, bucket sort) that beat that bound under structural assumptions about the data. For each you will trace the divide, sort, combine pattern (or its non-recursive equivalent), analyze best, average, and worst case, examine pivot strategies and partitioning schemes for quick sort, and see why heap sort runs in place. The lesson closes with the `O(n log n)` lower bound for comparison sorting and a quick tour of how built-in sorts (Timsort, V8) blend these techniques. In **Sorting (Elementary)**, you mastered the vocabulary of passes, swaps, invariants, and stability on `O(n^2)` algorithms. **Recursion Fundamentals** gave you the call-stack model that explains the `O(log n)` factor in merge and quick sort. Next, **Binary Search Templates** capitalize on sorted output to solve an entire class of medium-difficulty interview problems.