Part 2 of 14

Search and Sort

Linear search, binary search variants, comparison sorts, heap sort, linear sorts, quickselect. The first place algorithmic thinking shows up.

Chapters
8
Hours
2
Difficulty
Beginner to Intermediate
  1. 2.0beginner

    Linear search and what it's good for

    Linear search: when O(n) is the right answer, and the problems where the trick is recognising you don't need anything cleverer.

    15 min
  2. 2.1intermediate

    Binary search: the canonical version

    Binary search done right: the canonical template, off-by-one pitfalls, and the invariant you need to articulate before writing the loop.

    20 min
  3. 2.2intermediate

    Binary search variants: lower_bound, upper_bound, peaks, and rotated arrays

    Binary search beyond sorted arrays: lower_bound, upper_bound, first-true, last-true, and binary search on the answer space.

    20 min
  4. 2.3intermediate

    Comparison sorts I: insertion sort and merge sort

    Insertion, selection, and bubble sort: O(n^2) sorts, when each wins on real input, and the constant-factor lessons that hide inside them.

    15 min
  5. 2.4intermediate

    Comparison sorts II: quicksort, partition, and the production hybrids

    Merge sort and quicksort: divide-and-conquer, partitioning, stability, and why production library sorts are hybrid algorithms.

    20 min
  6. 2.5intermediate

    Heap sort and the n log n lower bound

    Heap sort and the binary heap: heapify, sift-up, sift-down, and why a heap is the right tool for k-way merges and priority queues.

    20 min
  7. 2.6intermediate

    Linear-time sorts: counting, radix, bucket

    Counting sort, radix sort, bucket sort: O(n) sorts that beat the comparison-sort lower bound when the input has structure.

    15 min
  8. 2.7intermediate

    Quickselect: linear-time selection

    Quickselect: O(n) average kth-smallest, partitioning, and the problems where you can dodge a full sort by selecting only the part you need.

    20 min