Study notes · 11% of the exam

Sorting and Searching

Know the properties of each sorting algorithm (time, space, stability, adaptivity), when non-comparison sorts beat n log n, and how to write binary search variants that always terminate and return the right boundary.

Key points

1
Merge sort is stable and always O(n log n) but needs O(n) extra space on arrays; quicksort is in place and usually fastest but degrades to O(n²) with bad pivots; heap sort is in place and O(n log n) but unstable.
2
Insertion sort is O(n) on nearly sorted input, and Python's Timsort detects sorted runs, so sorted() on presorted data makes only n − 1 comparisons.
3
Stable sorts let you sort by several keys: sort by the secondary key first, then by the primary key.
4
Comparison sorts need Ω(n log n) comparisons (⌈log₂ n!⌉); counting and radix sort avoid comparisons and run in O(n + k) or O(d(n + b)).
5
Binary search needs a range that strictly shrinks: if a branch sets lo = mid, use the upper middle (lo + hi + 1) // 2. bisect_left and bisect_right give the first and one-past-last positions of a value.
6
Binary search on the answer works whenever feasibility is monotonic (ship capacity, eating speed, kth value in a sorted matrix).
7
Quickselect finds the kth element in O(n) expected time; interval problems become linear scans after sorting by start.

Common traps

lo = mid with mid = (lo + hi) // 2 loops forever on a two-element range.
Last-element (or first-element) pivots make quicksort quadratic on sorted input, and Lomuto partitioning is quadratic on all-equal input.
bisect.insort is O(n) per insert because list insertion shifts elements, even though the search is O(log n).

Read the source

Test yourself on Sorting and Searching

Ten questions, with the answer and explanation after each one.