On this page

Module 2 · Searching & Sorting

Sorting is the most studied problem in computer science and still the most useful preprocessing step you can apply to data. Once an array is sorted, duplicates sit next to each other, the k-th smallest element is at index , two-pointer sweeps work, intervals can be merged in one pass, and any value can be found in comparisons instead of . Searching is the other half of the same idea: binary search is what sortedness buys you, and "binary search on the answer" turns a surprising number of optimisation problems into a sequence of yes/no questions.

Module 2 teaches both halves properly — not "here is quicksort" but why each algorithm is correct, exactly how many comparisons it makes, what it costs in memory and cache misses, and which of them actually runs inside Python, Java, C++, Go, Rust, PostgreSQL and your browser. The module is in the DSA: Zero to Mastery course. Previous module: Module 1 · Linear Data Structures. Next: Module 3 · Trees.

What this module covers

Ten lessons and a capstone, in three arcs.

Arc 1 — comparison sorting, from quadratic to optimal. The Sorting & Searching overview gives the landscape in one page. Elementary Sorts & Stability proves bubble, selection and insertion sort correct, counts their comparisons exactly, defines stability and shows why insertion sort still ships inside every production sort. Merge Sort & Inversion Counting is the cleanest divide-and-conquer algorithm you will meet: its recurrence, its exact comparison bound, and the inversion-counting trick that solves a family of "count pairs with a property" problems in . Quick Sort, Partition Schemes & Introsort covers Lomuto and Hoare partitions, three-way partitioning for duplicates, pivot choice and the trap introsort removes. Heap Sort gives in-place worst case and explains why it is rarely the fastest.

Arc 2 — beyond comparisons and into production. Non-Comparison Sorts & the Lower Bound proves that any comparison sort needs comparisons in the worst case, then beats that bound with counting, radix and bucket sort by not comparing at all. Sorting in the Real World opens up Timsort, pdqsort and std::sort, and shows external merge sort for data larger than RAM — the algorithm behind a database's "Sort Method: external merge".

Arc 3 — searching and selection. Binary Search Mastery is the lesson most people think they do not need and most people get wrong: half-open intervals, lower and upper bound, rotated arrays, search on the answer, real-valued and parallel binary search. Other Searches covers ternary search on unimodal functions, exponential search on unbounded input, interpolation search on uniform data and meet-in-the-middle. Quickselect, Median of Medians & Order Statistics finds the k-th smallest element in expected and proves the deterministic linear bound.

Capstone. A Sorting Library With Benchmarks: implement insertion, merge, quick (with an introsort fallback), heap and radix sort behind one interface, stress-test them against your language's built-in sort, then benchmark them on random, sorted, reversed and few-unique inputs and explain every curve.

Why in this order

Elementary sorts come first because they are the smallest algorithms on which to practise the skills the rest of the module needs: stating a loop invariant, counting operations exactly, and reasoning about inversions, the measure of how unsorted an array is. Insertion sort runs in for inversions; merge sort counts in ; quicksort's analysis sums over pairs that might be compared.

Merge sort precedes quicksort because its recurrence is the textbook Master-theorem case and its analysis needs no probability. The lower bound waits until four comparison sorts have all landed on , so that "can we do better?" is a real question. Searching comes after sorting because binary search is easiest once you see sorted order as a predicate that flips from false to true exactly once. Selection closes the module: quickselect is quicksort's partition used once, and median of medians is the module's hardest proof.

flowchart TD
    M1["Module 1 · Linear"] --> OV["Sorting & Searching overview"]
    OV --> ES["Elementary Sorts & Stability"]
    ES --> MS["Merge Sort & Inversions"]
    MS --> QS["Quick Sort & Introsort"]
    QS --> HS["Heap Sort"]
    HS --> NC["Non-Comparison Sorts & Lower Bound"]
    NC --> RW["Sorting in the Real World"]
    MS --> RW
    OV --> BS["Binary Search Mastery"]
    BS --> OS["Other Searches"]
    QS --> QSel["Quickselect & Order Statistics"]
    BS --> QSel
    RW --> CAP["Capstone: Sorting Library"]
    QSel --> CAP
    CAP --> M3["Module 3 · Trees"]

Arrows mean "read this first". The searching arc (binary search, other searches) depends only on the overview and can be studied in parallel with the sorting arc.

Prerequisites

From Module 0: Complexity Analysis — you will solve recurrences such as and should recognise the Master theorem; Recursion & Mathematical Induction — merge sort and quicksort are proved correct by strong induction on the input size; and Testing & Debugging Algorithms, because the single most effective way to debug a sort is a randomised comparison against the built-in one.

From Module 1: Two Pointers — the merge step is Family C of that lesson and the partition step is Family B — and Arrays & Strings for in-place array manipulation. How Data Structures Live in Memory explains the cache effects that decide which sort wins in practice. Code is in Python, Java, C++ and TypeScript, as in every module.

Lessons

#LessonAfter it you will be able to…Minutes
1Sorting & Searching (overview)Name the main sorts with their costs, pick one for a given constraint, write a correct binary search45
2Elementary Sorts & StabilityProve bubble, selection and insertion sort correct, count their comparisons exactly, explain stability and adaptivity40
3Merge Sort & Inversion CountingSolve the merge sort recurrence two ways, sort a linked list in extra space, count inversions and reverse pairs45
4Quick Sort, Partition Schemes & IntrosortWrite Lomuto, Hoare and three-way partitions, prove expected , explain how introsort bounds the worst case55
5Heap SortBuild a heap in , sort in place in worst case, explain why it loses to quicksort on real hardware35
6Non-Comparison Sorts & the Lower BoundProve the decision-tree bound and sort integers and strings in linear time with counting and radix sort50
7Sorting in the Real WorldExplain Timsort, pdqsort and std::sort, and sort data larger than memory with external merge sort45
8Binary Search MasteryWrite off-by-one-free lower/upper bound, search rotated arrays, and binary search on the answer60
9Other SearchesChoose ternary, exponential, interpolation search or meet-in-the-middle from the shape of the input40
10Quickselect, Median of Medians & Order StatisticsFind the k-th smallest in expected and prove the deterministic linear-time bound45
—Capstone: A Sorting Library With BenchmarksBuild, stress-test and benchmark five sorts behind one interface and explain the measured curves180

Lesson time totals about 460 minutes — seven and a half hours — plus three hours for the capstone and roughly as much again for the practice ladders. Two weeks at an hour a day is realistic; the searching arc can run in parallel if you have more time.

How to study this module

Count, do not estimate. The sorting lessons give exact comparison counts, checked by brute force over all permutations of small inputs. Instrument your own code with a counter and check, for example, that a reversed array of length 8 costs insertion sort exactly comparisons. A disagreement means an off-by-one somewhere.

Step through the visualizers, then trace by hand. Watch the embedded runs, then cover the trace table and reproduce it on paper. Sorting bugs are almost always boundary bugs.

Write the invariant as a comment before the loop. "a[0..i-1] is the original first i elements, sorted" is insertion sort's; "a[lo..i-1] <= pivot < a[i..j-1]" is Lomuto's. No sentence, no loop.

Stress-test against the built-in sort on thousands of random arrays of length 0 to 20 with many duplicates; they find more bugs than large inputs. Testing & Debugging Algorithms has the harness.

Measure on four input shapes — random, sorted, reversed, few unique — after each lesson, so that " average" versus "worst case" stops being abstract.

Practice ladders: first eight now, the hard tail later. Reverse pairs and count of range sum also have Fenwick-tree solutions (Module 3); solve them with merge sort now and come back.

Start with Sorting & Searching (overview), then follow the table in order. Previous module: Linear Data Structures. Course map: DSA: Zero to Mastery.