Counting Sort

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.