Module 2: Sorting, Searching & Fundamental Structures

Primary texts: The Algorithm Design Manual (Skiena) for problem-driven intuition and Introduction to Algorithms (CLRS) for proofs and cost analysis
Selective support: Algorithms (Sedgewick) for implementation texture; Grokking Algorithms for first-pass framing; Competitive Programming for exercise volume

This guide is the primary teacher. You do not need to read the source books front-to-back to complete this module. You do need to become fluent in sorting, searching, hashing, and heap-based priority queues -- both as algorithms and as a vocabulary for expressing cost tradeoffs.

Scope of This Module

This module is not a catalog of every sort ever invented. It is where you learn to reason about why a particular operation costs what it does and when to pay that cost.

What it covers in depth:

insertion, merge, and quicksort as contrasting comparison-sort designs
the Omega(n log n) lower bound proved through decision trees
linear-time specialty sorts (counting, radix) and the assumptions they pay for their speed with
external sorting resource accounting and verification of library contracts
binary search as an invariant-driven template, not a trick
selection and order statistics in linear time (quickselect, median-of-medians)
arrays vs linked lists vs trees vs hash tables as a choice about access patterns
hashing as a randomized model: expected O(1), universal hashing, load factor, collision resolution
binary heaps as implicit trees and the priority-queue API they enable
heapsort and the pattern-by-pattern use of priority queues in simulation, Dijkstra, top-K, median maintenance, and k-way merge

What it deliberately does not try to finish here:

balanced search trees beyond a mention (Module 5 handles them)
graph algorithms beyond naming Dijkstra as a PQ client (Module 3)
advanced amortized data structures (Module 5); reuse Module 1 analysis for resizing here
advanced heaps such as Fibonacci heaps (Module 5)

This is a foundations module. If you can implement these algorithms but cannot explain their cost profiles in a sentence, you are not done.

Before You Start

Complete the Prerequisite Diagnostic: tracing, induction, recurrences, expectation, and record identity. Repair failed prerequisites before the relevant cluster. Sorting stability, heaps and deletion are taught here; they are not required prior knowledge.

Budget 65–90 focused hours, roughly 7–9 weeks at 10 hours per week. This is an author estimate pending learner pilots. Prior experience may shorten the path; mastery evidence, not elapsed time, determines completion.

What This Module Is For

Sorting, searching, hashing, and priority queues are the plumbing of almost every non-trivial algorithm. Later work repeatedly asks:

how do I find one element or one order statistic out of many?
how do I organize data so that insert, lookup, and delete are all fast?
how do I keep track of the next-most-important item in a dynamic collection?
which algorithm costs what on which input distribution?
when does a library default hide a performance or correctness trap?

This module trains the reasoning needed for:

graph algorithms (Module 3) that use PQs for Dijkstra, Prim, A*
dynamic programming (Module 4) that often needs sorted input or fast lookup
advanced structures (Module 5) that generalize the "tree in an array" and amortization ideas introduced here
systems, database, and compiler work that depend on cache-aware sorting and hashing

You are learning to reason about data-handling cost precisely and pick the right tool for a job.

Concept Map

How To Use This Module

Work in order. Later clusters depend on earlier habits -- in particular the invariant-writing reflex from Cluster 1 and the probability-of-collision reasoning from Cluster 4.

Cluster 1: Comparison-Based Sorting and the Lower Bound

Order	Concept	Type	Focus
1	Insertion Sort Teaches Lessons That Survive	SUPPORTING	Invariants, adaptivity, and why library sorts switch to insertion sort on small subarrays
2	Mergesort Is the Divide-and-Conquer Exemplar	PRIMARY	Recurrence `T(n) = 2T(n/2) + Theta(n)`, stability, and guaranteed `O(n log n)`
3	Quicksort and Why Randomization Helps	PRIMARY	Partition, expected `O(n log n)`, pivot choice, adversarial vs unlucky inputs
4	Comparison Sorting Has an Omega(n log n) Lower Bound	PRIMARY	Decision trees, `log2(n!)`, and what counts as a "comparison"

Cluster mastery check: Can you write a loop invariant, derive Theta(n log n) from the mergesort recurrence, and explain why no comparison-based sort can do asymptotically better?

Cluster 2: Linear-Time and Specialized Sorting

Order	Concept	Type	Focus
5	Counting Sort and When Integer Keys Break the Lower Bound	SUPPORTING	`Theta(n + R)` stable record sorting, range width, and comparison-model assumptions
6	Radix Sort and Linear in Key Width	SUPPORTING	LSD vs MSD, the real meaning of "linear," and how radix plugs into counting sort
7	External and Practical Sorting	SUPPORTING	Library contracts, memory budgets, run generation, merge passes, and I/O accounting

Cluster mastery check: Can you pick the right sort given the input shape, key structure, and memory budget -- and justify why the textbook asymptotics alone do not decide?

Cluster 3: Searching in Sorted and Unsorted Data

Order	Concept	Type	Focus
8	Binary Search and Its Invariant	PRIMARY	The correctness template that generalizes to `lower_bound`, `upper_bound`, and predicate-based search
9	Selection and Order Statistics in O(n)	PRIMARY	Quickselect, median-of-medians, and the partition primitive as a general tool
10	Search-Data-Structure Choice	SUPPORTING	Array vs linked list vs balanced BST vs hash table, by access pattern

Cluster mastery check: Can you state the invariant for a binary search before writing any code, and can you match a storage shape to its operation-cost profile?

Cluster 4: Hash Tables as a Dictionary Primitive

Order	Concept	Type	Focus
11	Hashing as a Randomized Model	PRIMARY	Expected `O(1)` as a probabilistic guarantee, and what breaks it
12	Collision Resolution: Chaining vs Open Addressing	PRIMARY	Two schemes, their load-factor behavior, and deletion traps
13	Universal Hashing, Load Factor, and Resizing	SUPPORTING	Universal families, cryptographic vs non-cryptographic hashing, amortized resizes

Cluster mastery check: Can you explain why hash-table O(1) is expected rather than worst case, and can you distinguish a fixed-key random-hash guarantee from adversarial behavior?

Cluster 5: Heaps and Priority Queues

Order	Concept	Type	Focus
14	The Binary Heap as an Implicit Tree	PRIMARY	Array-backed heap layout, sift-up/down, and the `O(n)` build argument
15	Heapsort and the Priority-Queue API	PRIMARY	In-place heapsort, identity, stable ties, and indexed versus lazy updates
16	Priority-Queue Applications	SUPPORTING	Event simulation, Dijkstra relaxation, top-K, median maintenance, `k`-way merge

Cluster mastery check: Can you spot a problem whose loop is "pick the best remaining element, do work, possibly produce new elements," and translate it to a heap-backed priority queue?

Then work these practice pages:

Order	Practice path	Focus
1	Sorting Correctness and Analysis Lab	Invariants, complexity derivations, stability, and complexity-distinguishing drills
2	Searching and Selection Workshop	Binary search variants, quickselect, predicate-based search
3	Hashing and Priority-Queue Clinic	Collision reasoning, universal hashing, heap operations, PQ applications
4	Implementation and Transfer Studio	Resource budgets, event identity, integer representations, and streaming transfer

Use Module Quiz after the concept and practice path. Use Reference and Selective Reading and Learning Resources only for targeted reinforcement.

Learning Objectives

By the end of this module you should be able to:

Derive insertion-sort and partition invariants, and implement stable mergesort independently.
Derive the Theta(n log n) cost of mergesort and the expected O(n log n) of randomized quicksort.
Prove the Omega(n log n) comparison-sort lower bound via decision trees.
Derive stable counting and radix passes with explicit representation costs; implement them on the integer-sorting extension path.
Choose the right sorting algorithm given input shape, key structure, memory budget, and stability needs.
Implement binary search and its variants (lower_bound, upper_bound, predicate-based) using the invariant template.
Implement quickselect and describe when linear-time selection beats sorting.
Implement linear probing with correct deletion and updates, compare it with chaining, and qualify load-factor and hashing guarantees.
Implement a binary-heap-backed priority queue with insert, extract_min, peek, and understand how decrease_key is typically supported.
Identify priority-queue patterns in real problems: simulation, shortest path, top-K, median maintenance, k-way merge.

Outputs

Six runnable components across four labs: stable merge sort, equal range, selection, a map, a heap, and a streamed merge.
Sixteen practice problems with derivations, traces, counterexamples, and feedback from the separate solutions.
One evidence document separating proofs, finite checks, measured behavior, and assumptions; retain actual mistakes and repairs without an arbitrary quota.
One event-pipeline capstone, including a changed requirement and honest accounting for dictionary state as well as merge state.
One independent eight-competency assessment and a delayed fresh transfer task.

Completion Standard

Use Competencies, Evidence, and Remediation. Require at least level 2 in every competency, passing lab contracts, source review for complexity, and an independent explanation. Repair critical errors and attempt fresh tasks. Do not equate first-try memorized code with mastery or average away a missing skill.

Use Contracts, Representation, and Performance to qualify implementation and benchmarking claims. Extend with stable integer sorting, BFPRT, cancellation, or buffered external merge after the core requirements pass.

Reading Policy

Concept pages are the main path.
Local book chunks are selective reinforcement, not a second syllabus.
Read only if stuck means try the concept page, self-check, and drill first.
Optional deep dive means additional nuance or exercise volume, not required progression.
Primary external sources are collected in resources.md; concept pages link to course book indexes and bounded assignments.

Suggested Study Sequence

Stage	Focus	Estimated focused hours
Entry and concepts	Diagnostic, 16 lessons, targeted book reinforcement, engineering contracts	24–32
Guided implementations	Four labs with proofs, failures and repairs	14–20
Independent practice	P1–P16 and solution review	14–20
Assessment and remediation	Independent attempt, review, fresh rechecks and delayed transfer	7–10
Integration	Event-pipeline capstone and changed requirement	6–8

Total: 65–90 hours. Pause for remediation where needed. The optional depth path is additional work; it should answer a specific engineering question.

Reference

For book indexes, topic assignments, and the local collection map, use Reference and Selective Reading.

Rich Learning Pages

Model Artifact Calibration

For benchmark calibration, compare your measurements and decision writeup to the algorithm benchmark note model artifact.

Scope of This Module​

Before You Start​

What This Module Is For​

Concept Map​

How To Use This Module​

Cluster 1: Comparison-Based Sorting and the Lower Bound​

Cluster 2: Linear-Time and Specialized Sorting​

Cluster 3: Searching in Sorted and Unsorted Data​

Cluster 4: Hash Tables as a Dictionary Primitive​

Cluster 5: Heaps and Priority Queues​

Learning Objectives​

Outputs​

Completion Standard​

Reading Policy​

Suggested Study Sequence​

Reference​

Rich Learning Pages​

Model Artifact Calibration​

Assessment and Review Navigation​