Quick Sort

Plain quick sort with a fixed pivot is `O(n log n)` on random input but `O(n^2)` on already-sorted input, the worst-case input an adversary can hand it. Pick the pivot uniformly at random instead, and the same algorithm becomes `O(n log n)` _expected_ on every input, because the adversary no longer knows where the algorithm will partition. Randomization is not a hack here; it is a principled way to break the dependency between input and runtime. **Randomized Algorithms** trains that style of thinking. You will distinguish Las Vegas algorithms (always correct, randomized running time) from Monte Carlo algorithms (bounded running time, possibly wrong) and reason about expected-value guarantees. You will analyze Randomized Quick Sort to see why expected `O(n log n)` is robust against adversarial input, implement Quick Select for `O(n)` expected-time kth-element selection plus the deterministic median-of-medians variant, and walk through Reservoir Sampling Algorithm R for uniformly sampling `k` elements from a stream of unknown length, including the proof of uniformity. The lesson also revisits skip lists and treaps from the data-structures track as randomized alternatives to balanced BSTs. In **Sorting (Elementary)**, you saw worst-case-sensitive sorting. **Recursion Fundamentals** gave you the call-stack model behind quick sort and quick select. This lesson injects controlled randomness into those frameworks. Next, **Approximation Algorithms** trades exactness for polynomial time on NP-hard inputs.

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.