# Data Structures Algorithms
All Data Structures Algorithms notes →1 — Binary Search
The iterative implementation worth having cold, the three classic bugs (overflow, boundary-convention mixing, non-shrinking updates), the leftmost/rightmost/rotated-array variants, and why Python's bisect module usually beats hand-rolling it.
10 — Selection Algorithms
Quickselect finds the k-th smallest element in expected O(n) by reusing quicksort's Lomuto partition and discarding, rather than recursing into, the side that can't contain the answer — plus median-of-medians, k-th-largest and top-k-as-a-set variants, and the heap-based streaming alternative.
2 — Binary Search on Answer
Binary searching over a monotonic answer space instead of an array — the generalization that unlocks a large class of optimization problems.
3 — Sorting Fundamentals
The four axes every sort gets judged on — stability, in-place vs. auxiliary space, adaptive vs. not, comparison-based vs. not — the Ω(n log n) comparison-sort lower bound proved by the decision-tree argument, Python's Timsort, and a trade-off preview of every algorithm the rest of this Part covers.
4 — Quick Sort
Lomuto partitioning traced step by step, a precise derivation of the O(n log n) average case and the O(n²) worst case, randomized and median-of-three pivot mitigations, and why quicksort is in-place but not stable.
5 — Merge Sort
Divide-and-conquer sort with guaranteed O(n log n) and stability, at the cost of O(n) auxiliary space.
6 — Heap Sort
In-place heap sort derived from the heap chapter's heapify and sift-down — a guaranteed O(n log n) worst case with O(1) auxiliary space, and why giving up stability and cache locality is the price of both.
7 — Counting Sort
Non-comparison sort that counts occurrences directly by value, its stable prefix-sum construction, and the O(n + k) trade-off that only pays off when the key range doesn't dwarf the input.
8 — Radix Sort
LSD radix sort processes multi-digit integers by running the previous chapter's stable counting sort once per digit, achieving O(d(n+k)) time by indexing on digits instead of comparing whole values.
9 — Bucket Sort
Non-comparison sort for real-valued, roughly uniformly distributed input — O(n + k) average case derived from expected per-bucket occupancy, an O(n²) worst case with no floor beneath it, and a stability property that depends on the whole pipeline, not the bucketing step alone.