Chapter map

Where this sits in CS 300. Chapter 3 is the longest chapter in the course and the densest conceptually. It does four things in sequence: (1) grounds data representation (bits, ASCII) so the later structures have a floor; (2) introduces data structures as named shapes for storing data; (3) introduces abstract data types as the interface-level view; (4) builds the vocabulary of algorithm runtime: linear vs. binary search, Big-O, and the sorting zoo. Every later chapter in this course assumes you can read " $O(n \log n)$ " and understand why.

What you add to your toolkit here:

A map of the course. The seven structures (array, linked list, tree, BST, heap, hash table, graph) are named and contrasted before you build any of them.
ADT thinking. Stacks, queues, sets, maps — the contract (interface) is what users care about; the data structure (implementation) is what you choose.
Big-O fluency. You can read, write, and justify complexity claims: linear search is $O(n)$ because it touches every element; binary search is $O(\log n)$ because each step halves the remaining range.
Seven sorting algorithms with their tradeoffs. Insertion, selection, shell (incremental); quicksort, merge sort (divide-and-conquer); radix (non-comparison). Knowing which to reach for is a high-frequency exam question.

Mastery checklist — you should be able to, without references:

Translate between bits, hex, and an ASCII character (e.g., 0x41 $\to$ ’A’).
State the interface of each ADT (List, Stack, Queue, Set, Map, Priority Queue) and give one concrete data structure that implements it.
Explain linear vs. binary search with the runtime for each on the worst case and the preconditions.
State the Big-O definition from memory (” $f(n) = O(g(n))$ iff there exist constants $c$ and $n_0 \ldots$ ”) and apply it to a small example.
Order the growth hierarchy: $1, \log n, n, n \log n, n^2, 2^n$ .
For each sort (insertion, selection, shell, quicksort, merge, radix), give best / average / worst / stable? / in-place? and the one sentence that explains the runtime.
Pick the right sort for a scenario: “small, nearly sorted,” “huge, RAM-bound,” “keys are integers with bounded range,” “must be stable.”

Looking ahead. Chapters 4-6 spend their entire budget building two or three of the structures from the list here (linked lists, hash tables, BSTs). Every performance claim in those chapters is phrased in Big-O, and most of the sort algorithms in 3.15-3.21 reappear as components (e.g., merge sort is the model for merging sorted linked lists in ch. 4).

3.1 Representing Information as Bits

Chapter 2 covered algorithms — the instructions that process data. Chapter 3 shifts the view to how data is represented in the first place. At the bottom of every stack, “data” is ultimately a sequence of tiny binary switches. This section is the ground-floor view: what a bit is, what a byte is, and how characters like ’A’ or ’Z’ get mapped onto patterns of bits.

Bits and bytes

Why bits

Every piece of data — an integer, a character, a pixel, a video frame, a neural network’s weights — gets ultimately stored as a pattern of bits. The question isn’t whether data is bits but which encoding the program uses to interpret those bits. Two different encodings can give the same pattern two different meanings:

ASCII: bits that mean characters

A subset of the ASCII table

The full ASCII table is 128 entries. A few useful patterns to commit to memory:

::: center Range (dec) Range (hex) Meaning

0—31 0x00—0x1F Control characters (non-printing) 32 0x20 Space 33—47 0x21—0x2F Punctuation: ! " # $ % & ’ ( ) * + , - . / 48—57 0x30—0x39 Digits ’0’—’9’ 58—64 0x3A—0x40 More punctuation: : ; < = > ? @ 65—90 0x41—0x5A Uppercase ’A’—’Z’ 91—96 0x5B—0x60 [ \ ] ^ _ ‘ 97—122 0x61—0x7A Lowercase ’a’—’z’ 123—126 0x7B—0x7E { | } ~ 127 0x7F DEL (control) :::

Digit-char to int, by hand

char c = '7';
int  d = c - '0';     // 55 - 48 == 7

// Accumulate digits from a string into a number:
int n = 0;
for (char ch : s) {
    if (std::isdigit(ch)) n = n * 10 + (ch - '0');
}

Case conversion without cctype

char upper = 'g' - 32;     // 'G'
char lower = 'G' + 32;     // 'g'
char flip  = 'G' ^ 32;     // 'g'
char flip2 = 'g' ^ 32;     // 'G'

Using std::toupper/std::tolower is still the right production choice — they handle the non-letter case and locale concerns correctly — but knowing the underlying bit trick helps when you read code that uses it.

What ASCII can’t do: everything else

ASCII encodes English. It has no code points for accented letters (é, ñ), no space for non-Latin scripts (Arabic, Chinese, Cyrillic, Tamil), and no emoji. The modern universal encoding is Unicode, which assigns code points up to $10FFFF_{16}$ ( $\sim 1.1$ million characters).

Connecting bits back to data structures

Every data structure you’re about to meet (linked list, stack, queue, tree, hash table) is ultimately a layout of bits in memory, organized so that the operations the structure promises are fast. A linked list stores a value plus a pointer-to-next-node; a vector stores an array of values plus a size and capacity; a hash table stores an array of buckets plus a hash function. The abstractions hide the bits, but understanding that the bits are still there — and that performance ultimately comes from how they’re arranged — is what separates “using” a data structure from choosing one.

3.2 Data Structures

A data structure is a way of organizing data in memory so that a particular set of operations (access, search, insert, delete) can be done efficiently. looked at how individual values are stored as bits; this section starts naming the ways those values get grouped into useful collections. The rest of the course is essentially a detailed tour of the seven structures listed here.

The seven structures you’ll meet this semester

Record (struct, class)

A group of named fields bundled into a single value. Fields can be of different types. In C++, a struct or class is a record.

struct Bid {
    std::string title;
    std::string fund;
    double amount;
};

Why there are so many

Every structure makes different operations fast at the cost of others. There is no “best” data structure; the right one depends on the operation mix you actually perform.

::: center Structure Access Insert mid Good for

Array / vector $O(1)$ $O(n)$ Random access, cache-friendly Linked list $O(n)$ $O(1)$ ^*^ Frequent insert/delete Hash table $O(1)$ avg $O(1)$ avg Fast keyed lookup Binary search tree $O(\log n)$ $O(\log n)$ Sorted iteration Heap --- $O(\log n)$ Always know the max/min Graph --- varies Relationships, networks :::

^*^Given a pointer to the insertion point. Finding the point is still $O(n)$ .

Balanced only. A degenerate BST is $O(n)$ .

A concrete example: the shift problem

The classic case where structure choice matters is inserting in the middle of a collection.

How to pick a data structure

The C++ standard library’s version of this list

Almost every structure named above already ships with the language. Know the mapping so you don’t reinvent:

::: center Concept C++ standard type

Array / vector std::vector<T>, std::array<T, N> Linked list std::list<T> (doubly) or std::forward_list<T> Hash table std::unordered_map<K, V>, std::unordered_set<T> Balanced BST std::map<K, V>, std::set<T> Heap / priority queue std::priority_queue<T> Stack / queue (adapters) std::stack<T>, std::queue<T> Graph no built-in — build from vector<vector<int>> or similar :::

3.3 Relation Between Data Structures and Algorithms

Chapter 2 treated algorithms in the abstract; section 3.2 laid out the main data structures. This section is the hinge between them. The relationship runs in two directions, and keeping both in mind is what turns “I know some algorithms” and “I know some structures” into “I can design software.”

Direction 1: Different structure, different algorithm

“Append an item” sounds like one operation, but the code behind it depends entirely on what you’re appending to. Compare appending to a linked list against appending to an array.

Append to a singly linked list -- O(1)

void append(Node*& head, Node*& tail, int value) {
    Node* n = new Node{value, nullptr};
    if (!head) {           // empty list
        head = tail = n;
    } else {
        tail->next = n;    // stitch onto the end
        tail = n;
    }
}

With a tail pointer cached, linking on a new node is a couple of pointer writes — no elements moved, no memory copied.

Append to a fixed-capacity array -- O(1) amortized, O(n) worst case

void append(int*& data, int& size, int& cap, int value) {
    if (size == cap) {
        int newCap = cap == 0 ? 1 : cap * 2;
        int* grown = new int[newCap];
        for (int i = 0; i < size; ++i) grown[i] = data[i];  // copy all
        delete[] data;
        data = grown;
        cap = newCap;
    }
    data[size++] = value;
}

Most appends just drop the value into the next slot. But whenever the array fills up, every existing element has to be copied into a larger block. std::vector hides this dance behind push_back, but the copy still happens.

Insert-at-front is the sharper example

Append hides a lot because both versions usually finish fast. Prepend makes the structure choice visible immediately.

::: center Operation Array / vector Singly linked list

Append at end $O(1)$ amortized $O(1)$ with tail pointer Insert at front $O(n)$ (shift all) $O(1)$ (new head) Random access a[i] $O(1)$ $O(i)$ (walk from head) Insert in middle (given iterator) $O(n)$ shift $O(1)$ relink :::

Same operation names, completely different runtimes. The structure you pick is the set of costs you accept.

Direction 2: Algorithms use structures as scratch space

The other direction: a larger algorithm almost always relies on a data structure to hold intermediate results. The structure you pick shapes the algorithm you write.

Example: top- $k$ salespersons. Given a list of salespeople, print the top 5 by sales total.

A small fixed-size array as running top-5

struct Rep { std::string name; double sales; };

void topFive(const std::vector<Rep>& all) {
    std::array<Rep, 5> top{};
    for (auto& r : top) r.sales = -1;        // sentinel

    for (const Rep& r : all) {
        if (r.sales > top.back().sales) {    // beats last in top-5
            top.back() = r;
            std::sort(top.begin(), top.end(),
                      [](const Rep& a, const Rep& b){
                          return a.sales > b.sales;
                      });
        }
    }
    for (const Rep& r : top) std::cout << r.name << " " << r.sales << "\n";
}

The fixed-size array is the data structure; the scan-and-swap pattern is the algorithm. The array’s job is to remember the current champions as we sweep through all candidates.

Different structure, different algorithm

If we used a different structure to hold the running top-5, the algorithm changes shape:

Min-heap of size 5. Peek at the minimum in $O(1)$ ; if the new candidate beats it, pop and push. Total $O(n \log k)$ but cleaner and faster than re-sorting an array.
Sorted linked list of size 5. Insert-in-order means walking the list to find the right slot — $O(k)$ per candidate that beats the minimum.
BST / std::set. Overkill here, but useful if $k$ were large or you needed dynamic queries.

Same problem, four different implementations, each dictated by the structure you choose.

Putting the two directions together

3.4 Abstract Data Types

The previous section showed that the same operation name on two different data structures hides two different algorithms. That’s a feature, not a bug. The whole point of this section’s central idea — the abstract data type — is to let us name an operation without naming an implementation, so code that uses the operation keeps working no matter which structure sits underneath.

Why the separation matters

Everyday analogy: “printer” is an ADT (print this page, cancel this job). Laser printer, inkjet, thermal, network printer — all different implementations. The program calling print() does not and should not care. Swap the printer, the program still works.

In code, the benefits land as:

Replaceability. Start with an array-backed list; switch to a linked-list-backed list when profiling tells you to. No caller code changes.
Reasoning. The correctness of caller code depends on the ADT’s contract, not on representation details.
Teamwork. One person builds the ADT, another builds against its interface. They negotiate a contract, not a memory layout.

The standard ADTs you should recognize

The textbook lists nine common ADTs. Treat this table as a vocabulary list — each one gets its own chapter later.

::: center ADT What the contract says Usual implementations

List Ordered sequence; append, remove, search, traverse. Array, linked list Dynamic array Ordered with $O(1)$ indexed access; grows on demand. Array (with resize) Stack LIFO; push / pop / peek at the top only. Array, linked list Queue FIFO; enqueue at back, dequeue from front. Linked list, circular array Deque Insert/remove at both ends. Doubly linked list, circular array Bag Unordered collection; duplicates allowed. Array, linked list Set Unordered; no duplicates. BST, hash table Priority queue Queue where highest-priority item comes out first. Heap Dictionary / Map Key $\to$ value lookup. Hash table, BST :::

C++ makes the ADT/structure distinction concrete

The C++ standard library names ADTs via container adaptors that sit on top of underlying containers. This is worth seeing explicitly because it’s the same idea the textbook is describing, except made literal in the type system.

std::stack is an ADT built on another container

#include <stack>
#include <vector>
#include <list>

std::stack<int>                     s1;  // default: uses std::deque
std::stack<int, std::vector<int>>   s2;  // uses a vector
std::stack<int, std::list<int>>     s3;  // uses a linked list

s1.push(3); s1.push(4);
int top = s1.top();  // 4
s1.pop();

All three behave identically from the caller’s point of view: a stack. What differs is the underlying storage. The ADT (stack) is the interface; the structure is a template parameter.

The library’s ADT / structure mapping

::: center ADT (from textbook) C++ name Default structure

List std::list, std::forward_list Doubly / singly linked list Dynamic array std::vector Contiguous array Stack std::stack std::deque Queue std::queue std::deque Deque std::deque Chunked array Set std::set, std::unordered_set BST / hash table Priority queue std::priority_queue Binary heap over std::vector Map std::map, std::unordered_map BST / hash table :::

(C++ doesn’t ship a “bag” type; a std::vector or std::multiset fills that role.)

Using ADTs to keep caller code honest

Algorithm expressed against an ADT

// Reverse the order of items in any container via a stack.
template <typename Container>
void reverseInPlace(Container& c) {
    std::stack<typename Container::value_type> buf;
    for (auto& x : c) buf.push(x);   // push all
    for (auto& x : c) {              // pop back into place
        x = buf.top();
        buf.pop();
    }
}

This works for any container. The algorithm depends only on the stack ADT — push, top, pop. Whatever storage std::stack uses, the reverse works.

3.5 Applications of ADTs

Section 3.4 made the ADT/structure distinction; this section asks what you get from keeping them separate. Two payoffs: abstraction simplifies programming, and standard libraries mean you rarely implement the common ADTs by hand. The catch — which this section also makes explicit — is that abstraction does not free you from thinking about efficiency.

Abstraction as a productivity lever

Abstraction buys three compounding benefits once you’re comfortable with it:

Less code to write. You describe what you want, not how to do it. map[key] = value hides a hash computation, bucket lookup, collision handling, and possible rehash.
Less code to read. A colleague scanning your code sees the ADT’s operations and immediately knows the shape of the data flow — “oh, it’s a queue, so FIFO” — without studying a custom linked-list implementation.
Less code to debug. Bugs in the ADT’s implementation live in one place; bugs in your algorithm live in yours. The two don’t mix.

Same job, two abstraction levels

// Low-level: roll our own LIFO using a raw array + top index.
int stack[100];
int top = -1;
stack[++top] = 3;
stack[++top] = 4;
int x = stack[top--];          // 4
int y = stack[top--];          // 3

// High-level: lean on the stack ADT from the STL.
#include <stack>
std::stack<int> s;
s.push(3);
s.push(4);
int x = s.top(); s.pop();       // 4
int y = s.top(); s.pop();       // 3

Both snippets do the same thing. The first mixes the algorithm with the storage. The second talks only in stack operations — push, top, pop — so a reader grasps the intent in one pass.

ADTs in standard libraries

Almost every modern language ships an implementation of the common ADTs as part of its standard library. You rarely implement a queue or a hash map from scratch in production; you use the language’s provided one.

::: center Language Library ADTs you get

C++ Standard Template Library (STL) vector, list, deque, stack, queue, priority_queue, set, map, unordered_set, unordered_map Python Built-ins + collections list, tuple, set, dict, deque, defaultdict, Counter, heapq Java Java Collections Framework (JCF) ArrayList, LinkedList, HashSet, TreeSet, HashMap, TreeMap, ArrayDeque, PriorityQueue :::

Why CS 300 still has you build them by hand

Production code uses the standard library. This course has you implement linked lists, hash tables, heaps, and trees from scratch. That’s deliberate, and for two reasons.

Choosing the right ADT is the actual skill

Because the common ADTs are available off the shelf, the hard part isn’t implementing them — it’s recognizing which one the problem in front of you is asking for.

::: center Problem shape ADT

“I need the most recent item first.” Stack “I need the oldest waiting item first.” Queue “I need the most important item first.” Priority queue “I need fast lookup by a key.” Map / dictionary “I need a collection of distinct items, order doesn’t matter.” Set “I need ordered access by index.” Dynamic array / list :::

3.6 Searching and Algorithm Runtime

This section restarts the algorithms thread now that we have a vocabulary of data structures to search through. The worked example is linear search, the simplest search algorithm there is. The real payoff of the section, though, is the first careful look at runtime as a function of input size — the idea that turns into Big-O in .

Linear search

Linear search in C++

int linearSearch(const std::vector<int>& nums, int key) {
    for (std::size_t i = 0; i < nums.size(); ++i) {
        if (nums[i] == key) {
            return static_cast<int>(i);
        }
    }
    return -1;  // not found
}

int main() {
    std::vector<int> nums = {2, 4, 7, 10, 11, 32, 45, 87};
    int idx = linearSearch(nums, 10);
    if (idx == -1) std::cout << "not found\n";
    else           std::cout << "found at index " << idx << '\n';
}

Why linear — and when it’s fine

Linear search makes no assumptions about the data. It works on an unsorted array, a linked list, or any sequence you can iterate once. That’s the whole point: it’s the baseline.

Best case. Key is at index 0 — 1 comparison.
Worst case. Key is last, or absent — $n$ comparisons.
Average case. On uniformly random hit positions, roughly $n/2$ comparisons. When the key is absent, always $n$ .

Runtime as a function of input size

The key idea the textbook introduces here: runtime grows with the size of the input. Counting actual seconds depends on the machine. Counting the number of operations the algorithm does is a machine-independent proxy that predicts the seconds.

Concrete numbers

The scale at which " $O(N)$ " starts to feel slow surprises people the first time they see it. Suppose one comparison takes 1 microsecond ( $10^{-6}$ s).

::: center $N$ Worst-case comparisons Wall time @ 1 s each

$10^3$ 1,000 0.001 s $10^6$ 1,000,000 1 s $10^7$ $10^7$ 10 s $2 \times 10^8$ (Amazon’s catalog, ish) $2 \times 10^8$ 200 s $\approx$ 3 min 20 s $10^9$ $10^9$ about 17 min :::

Ignoring constants: why we say “on the order of $N$ ”

If your linear search does 3 operations per element (bounds check, array access, comparison) instead of 1, the constant changes but the shape of the growth does not: doubling $N$ still doubles the work.

Searching, structures, and algorithms together

The textbook frames this section as “algorithms,” but notice how much depends on the structure underneath. Linear search is the universal baseline because it makes no assumptions. If you know more about the structure, you can do much better:

::: center What you know about the data Algorithm Worst case

Nothing; unsorted sequence Linear search $O(N)$ Array is sorted Binary search $O(\log N)$ Data lives in a hash table keyed by what you’re searching for Hash lookup $O(1)$ expected Data lives in a balanced BST keyed by the search value BST lookup $O(\log N)$ :::

3.8 Binary Search

Section 3.6 covered linear search — the universal baseline. This section introduces the first algorithm that does substantially better: binary search. The catch, and the whole point, is that it only works if the data is sorted and randomly accessible. That trade-off — accept a precondition on the structure, unlock a much faster algorithm — is a pattern you will see repeatedly for the rest of the course.

The idea

Think about how you find a name in a physical phone book. You don’t read from the beginning. You open near the middle, see whether your target comes before or after, and immediately ignore the half that doesn’t contain it. Repeat.

Binary search in C++

Iterative binary search

int binarySearch(const std::vector<int>& nums, int key) {
    int low = 0;
    int high = static_cast<int>(nums.size()) - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;   // overflow-safe midpoint
        if      (nums[mid] == key) return mid;
        else if (nums[mid]  < key) low  = mid + 1;
        else                       high = mid - 1;
    }
    return -1;  // not found
}

The textbook writes (low + high) / 2. That formula can overflow when low + high exceeds INT_MAX. The idiomatic fix is low + (high - low) / 2, which computes the same midpoint without the intermediate sum blowing up.

Recursive binary search

Binary search is also the textbook example of a recursive algorithm that calls itself on a shrinking problem.

Recursive binary search

int binarySearch(const std::vector<int>& nums,
                 int key, int low, int high) {
    if (low > high) return -1;                 // base case
    int mid = low + (high - low) / 2;
    if (nums[mid] == key) return mid;
    if (nums[mid]  < key) return binarySearch(nums, key, mid + 1, high);
    return                   binarySearch(nums, key, low, mid - 1);
}

Same algorithm; two views. The iterative version updates a window; the recursive version calls itself on a smaller window. The iterative version is usually preferred in C++ because it avoids stack frames.

Why $O(\log n)$

Why \log n is so dramatic

The concrete comparison with linear search is what sells binary search. One comparison at 1 s:

::: center $N$ Linear worst Binary worst Ratio

$10^3$ 1,000 ops (1 ms) 10 ops (10 s) 100 $\times$ $10^6$ $10^6$ ops (1 s) 20 ops (20 s) 50,000 $\times$ $2 \times 10^8$ $2 \times 10^8$ (3+ min) 28 ops (28 s) $\approx 7 \times 10^6$$\times$ $10^9$ $10^9$ ops ( $\approx$ 17 min) 30 ops (30 s) $\approx 3 \times 10^7$$\times$ :::

The bigger lesson

3.9 Constant-Time Operations

Binary search was the first algorithm where the number of operations mattered more than the speed of the processor. This section makes precise what “one operation” even means for runtime analysis. The short answer: we count constant-time operations — the unit of work the CPU can do in a fixed time independent of input values.

What counts as constant time

The short list of things that are typically $O(1)$ on a modern processor:

::: center Operation Why it’s constant

Arithmetic on fixed-size numeric types (int, double) Hardware does it in a bounded number of cycles regardless of values. Assignment of a fixed-size value (scalar, pointer, reference) Copies a fixed number of bytes. Comparison of fixed-size values One CPU instruction. Indexed access to an array element (a[i]) One pointer arithmetic + one memory load. Push / pop on a std::vector (amortized) Constant on average; occasional resize is paid for across many pushes. Hash-table lookup (expected) One hash computation + one bucket probe on average. Dereferencing a pointer One memory load. Reading the length stored by a container (v.size()) Returns a cached value. :::

Operations that look simple but aren't constant time

std::string a(1'000'000, 'x');
std::string b(1'000'000, 'y');

std::string c = a + b;          // O(n) -- allocates and copies
std::string d = a;              // O(n) -- copy constructor
bool same = (a == b);           // O(n) -- compares every character
int count = std::count(v.begin(), v.end(), 3);  // O(n)

The +, =, and == operators look like one operation at the language level, but they walk every character of every string. The source code has constant width; the runtime does not.

Why fixed size matters

Notice the repeating phrase: “fixed-size integer or floating-point values.” A modern CPU’s adder has a fixed number of bits — 32 or 64 — and its time-per-add doesn’t depend on whether the operands are 3 or 2,147,483,646.

Counting the right things

In runtime analysis we don’t count every line of code. We pick a representative operation and count how many times it runs.

The hidden-loop trap

Watch for hidden loops inside library calls

for (std::size_t i = 0; i < n; ++i) {
    std::string msg = "item " + std::to_string(i);  // O(len)
    output += msg;                                   // O(|output|)
}

This is not $O(n)$ . The output += msg concatenation grows more expensive each iteration because |output| keeps growing. Total work is $O(n^2)$ . A reader counting “one loop, so linear” gets the answer spectacularly wrong.

The rule of thumb

3.10 Growth of Functions and Complexity

Section 3.9 defined the unit of measurement: constant-time operations. This section asks how the count of those operations grows as the input grows. That growth is what we summarize with Big-O (and its cousins $\Omega$ , $\Theta$ ). These are the three core pieces of vocabulary that will structure every runtime claim for the rest of the course.

Best case, worst case, and $T(N)$

For an algorithm running on input of size $N$ , the number of constant-time operations it performs is a function of $N$ . We’ll call that function $T(N)$ . Usually $T(N)$ depends on more than just $N$ — it depends on which particular input of size $N$ we’re running on. Hence the standard two-sided view:

Upper and lower bounds

Rather than carrying the exact $T(N)$ formula around (with all its constants and lower-order terms), we bound it with simpler functions.

Asymptotic notation: strip the constants

For cross-algorithm comparison we don’t care about the constants in front of $N^2$ . We care that it’s an $N^2$ . That’s what Big-O, $\Omega$ , and $\Theta$ formalize: rate of growth, constants and lower-order terms absorbed.

Little-oh and little-omega: when the bound is strictly looser

$O$ and $\Omega$ may or may not be tight — $2n = O(n^2)$ is true (linear grows no faster than quadratic), but it’s also a loose bound. CLRS introduces two more notations for the strictly-looser case:

$f(n) = o(g(n))$ (little-oh): for every positive constant $c$ , there exists $n_0$ such that $f(n) < c \cdot g(n)$ for all $n \ge n_0$ . Equivalently, $\lim_{n\to\infty} f(n)/g(n) = 0$ . Strict upper bound.
$f(n) = \omega(g(n))$ (little-omega): the mirror image. $\lim_{n\to\infty} f(n)/g(n) = \infty$ . Strict lower bound.

The cleanest mental model is the analogy with real-number comparisons:

::: center

$f = O(g)$ like $f \le g$ $f = \Omega(g)$ like $f \ge g$ $f = \Theta(g)$ like $f = g$ $f = o(g)$ like $f < g$ (strict) $f = \omega(g)$ like $f > g$ (strict)

:::

So $2n = O(n^2)$ AND $2n = o(n^2)$ — the latter is the precise statement (linear is strictly smaller than quadratic). $2n = O(n)$ is also true, but $2n \ne o(n)$ — linear is not strictly smaller than itself. Use $o$ and $\omega$ when you want to signal “definitely not just a loose bound.”

What c and N_0 buy you

The constant $c$ absorbs the hardware, the language, and any constant-factor overhead. The threshold $N_0$ lets us ignore small inputs, where lower-order terms and one-time setup costs distort the picture.

How to read a big-O claim

The growth-rate hierarchy

For large $N$ , the following functions are ordered by how fast they grow. Every entry dominates the ones above it.

::: center Class Name Examples

$O(1)$ Constant Array index, hash lookup $O(\log N)$ Logarithmic Binary search, balanced-BST lookup $O(N)$ Linear Linear search, one pass over an array $O(N \log N)$ Linearithmic / ” $N$ log $N$ ” Merge sort, heap sort, good sorts $O(N^2)$ Quadratic Bubble sort, insertion sort worst case, nested loops $O(N^3)$ Cubic Naive matrix multiply, certain DP algorithms $O(2^N)$ Exponential Brute-force subset enumeration $O(N!)$ Factorial Brute-force permutations (traveling salesman) :::

In practice

Halfway recap -- before we dive into sorts

You’ve now been through the first half of ch. 3. Before sorting algorithms start piling up, consolidate:

What you’ve built (3.1-3.10):

Bits & ASCII. Data in memory is bits; characters are just small integers with an agreed table. You can move between char, int, and cctype classification without friction.
Seven data structures named. Array, linked list, tree, BST, heap, hash table, graph. You can’t implement them all yet, but you know their names and what shape of problem each is good for.
ADT vs. data structure. An ADT is the contract (“a stack has push/pop/top” --- no mention of how). A data structure is the implementation. Every C++ STL container is an ADT realized by one or more data structures (std::stack<T> is an ADT; its default implementation is std::deque<T>).
Two searches contrasted. Linear search is $O(n)$ and works on any data. Binary search is $O(\log n)$ but requires sorted data --- which motivates the next half of the chapter.
Big-O as a working tool. You can read “constant time,” “logarithmic,” “linear,” “quadratic,” “exponential” and point at the growth-rate hierarchy.

The through-line into sorting. Binary search is the payoff of sorted data. That makes “how expensive is sorting?” the immediate follow-up question: if sorting costs $O(n \log n)$ and then you do one search at $O(\log n)$ , you’ve paid more than linear search ( $O(n)$ ) for one lookup --- so sorting only pays when you search many times. Every sort in the next half of the chapter is a different attempt to make that one-time cost as small as possible.

What’s ahead (3.14-3.21): seven sorting algorithms plus a fast-sort overview. They split into three families:

Incremental: bubble (covered in ch_13 extras as pedagogy-only), insertion, selection, shell --- easy to code, $O(n^2)$ (except shell).
Divide-and-conquer: merge sort, quicksort --- $O(n \log n)$ average; the ones you’ll actually ship.
Non-comparison: radix sort --- $O(n k)$ , fast when $k$ (key width) is small.

If any of 3.1-3.10 still feels shaky, stop here and re-read. The sorting analyses that follow all lean on the Big-O definition and the growth-rate hierarchy. You don’t need mastery yet; you need enough fluency that “this loop is $O(n)$ ” and “this outer-over-inner loop is $O(n^2)$ ” don’t slow you down.

3.14 Sorting: Introduction

Searching (3.6, 3.8) was the first algorithmic problem we analyzed. Sorting is the second, and it’s arguably the more important one: binary search, priority queues, deduplication, many-pass merges, and much of computational geometry all assume data you can sort first. This short section sets the stage; the rest of this chapter walks through insertion, selection, shell, quicksort, merge, and radix sort. (Bubble sort lives in ch_13’s extras chapter, since it is pedagogy-only; heap sort waits for ch_7, once we have heaps.)

Why sorting is its own field

Sorting is the most-studied algorithmic problem in computer science. It looks trivial at small sizes — you could do it by hand — and turns out to be surprisingly deep.

The fundamental constraint

Why isn’t sorting just “put each element in its right slot”? Because the program doesn’t know where the right slot is without doing work to find out.

Swap as the atomic move

void swap(int& a, int& b) {
    int tmp = a;
    a = b;
    b = tmp;
}

// Or just:
std::swap(a, b);

Almost every comparison-based sort boils down to compare-two, swap-if-needed, repeated in different patterns. Bubble sort scans adjacent pairs. Selection sort finds the minimum of a suffix and swaps it into place. Insertion sort shifts a value leftward through an already-sorted prefix. Quicksort partitions around a pivot. Merge sort combines sorted halves.

What makes sorts differ

When we compare two sorting algorithms we ask five questions:

::: center Property What it means

Time complexity Best / average / worst-case count of comparisons and swaps as a function of $n$ . Space complexity Extra memory beyond the input. In-place sorts use $O(1)$ extra; merge sort needs $O(n)$ . Stability Does the sort preserve the original order of equal elements? Useful when you’ve already sorted by a secondary key. Adaptivity Does it run faster on already-mostly-sorted input? Access pattern Does it need random access (quicksort, binary search during sort) or sequential only (merge sort)? :::

Faster-than-comparison sorts

In C++

The library already sorts

#include <algorithm>
std::vector<int> v = {17, 3, 44, 6, 9};
std::sort(v.begin(), v.end());                     // ascending: 3 6 9 17 44
std::sort(v.begin(), v.end(), std::greater<int>()); // descending

std::stable_sort(v.begin(), v.end());               // preserves equal-order
std::partial_sort(v.begin(), v.begin() + 3, v.end()); // only first 3 sorted

std::sort is typically an introsort: quicksort that switches to heap sort when recursion gets too deep. Worst-case $O(n \log n)$ , average $O(n \log n)$ with a tiny constant. For production code, start here.

3.15 Insertion Sort

Insertion sort is the first concrete sorting algorithm we’ll build. It’s the sort most people naturally perform by hand — think about how you’d organize a hand of playing cards — and its quadratic worst-case cost is the price of its simplicity. It’s also surprisingly good when the input is already nearly sorted, and that adaptivity is where it shines.

The idea

Insertion sort in C++

Swap-based insertion sort

void insertionSort(std::vector<int>& nums) {
    for (std::size_t i = 1; i < nums.size(); ++i) {
        std::size_t j = i;
        while (j > 0 && nums[j] < nums[j - 1]) {
            std::swap(nums[j], nums[j - 1]);
            --j;
        }
    }
}

The outer loop marks the boundary between sorted and unsorted. The inner loop walks nums[i] leftward one swap at a time until its left neighbor is no larger.

Shift-based insertion sort (one fewer write per step)

void insertionSort(std::vector<int>& nums) {
    for (std::size_t i = 1; i < nums.size(); ++i) {
        int key = nums[i];
        std::size_t j = i;
        while (j > 0 && nums[j - 1] > key) {
            nums[j] = nums[j - 1];   // shift right
            --j;
        }
        nums[j] = key;               // drop key into place
    }
}

Instead of swapping pairs (three writes each), this version shifts and then drops the key once. Same algorithm, measurably faster constant factor.

Worst-case analysis: $O(n^2)$

Best case: $O(n)$ on already-sorted input

Nearly sorted lists

The adaptivity generalizes. Suppose only a constant number $c$ of elements are out of place. Then

$n - c$ elements each need 1 comparison to stay put.
$c$ elements each need at most $n$ comparisons.

Total work: $(n - c) \cdot 1 + c \cdot n = n - c + cn \in O(n)$ (since $c$ is constant). Insertion sort runs in linear time on nearly-sorted input.

Why this matters in practice

Properties

::: center Property Insertion sort

Best case $\Theta(n)$ — already-sorted input Worst case $\Theta(n^2)$ — reverse-sorted input Average case $\Theta(n^2)$ for random input Space $O(1)$ extra — in-place Stable? Yes — equal elements retain original order Adaptive? Yes — fast on nearly-sorted input :::

Loop invariants: the formal correctness-proof technique

The intuitive argument “insertion sort works because each pass extends the sorted prefix by one” is a loop invariant proof, just stated informally. CLRS Ch 2.1 makes this rigorous — the same 3-part structure works for every loop-based algorithm in this course (binary search, BST insert, Dijkstra, …).

The technique. For insertion sort’s outer loop, the invariant is:

At the start of each iteration, the subarray nums[0..i-1] contains the original first $i$ elements, sorted in non-decreasing order.

A complete proof has three parts:

Initialization. The invariant holds before the first iteration. Here: i = 1, so the prefix is nums[0..0] — one element, trivially sorted.
Maintenance. If the invariant holds at the start of one iteration, it holds at the start of the next. Here: the inner while loop slides nums[i] leftward past anything larger; when it stops, the prefix nums[0..i] is sorted. Increment i; invariant restored for next iteration.
Termination. When the loop exits, the invariant plus the exit condition imply the desired result. Here: i == nums.size(), so the entire array is the sorted prefix.

That’s a complete correctness argument. The same scaffold scales to harder algorithms — binary search’s invariant is “the target, if present, lies in [lo, hi]”; BST search’s is “the target, if present, lies in the subtree rooted at the current node.” Once you can state the invariant, the proof writes itself.

3.16 Selection Sort

Selection sort is insertion sort’s mirror image. Both carve the array into a sorted prefix and an unsorted suffix; both extend the prefix by one element per outer-loop pass. The difference is which element gets placed each pass. Insertion sort takes whatever is next and slides it into position. Selection sort picks the smallest element of the remaining unsorted region and parks it at the end of the sorted region.

Selection sort in C++

Selection sort

void selectionSort(std::vector<int>& nums) {
    for (std::size_t i = 0; i + 1 < nums.size(); ++i) {
        std::size_t indexSmallest = i;
        for (std::size_t j = i + 1; j < nums.size(); ++j) {
            if (nums[j] < nums[indexSmallest]) {
                indexSmallest = j;
            }
        }
        std::swap(nums[i], nums[indexSmallest]);
    }
}

Outer loop advances the boundary. Inner loop scans the suffix and records the index of the smallest. One swap per outer iteration places it.

Why it always does $\Theta(n^2)$ comparisons

Where selection sort is better than insertion sort

Selection sort has one redeeming feature: it does at most $n - 1$ swaps total. Insertion sort can do $\Theta(n^2)$ swaps.

Selection sort vs. insertion sort at a glance

::: center Property Insertion sort Selection sort

Best case $\Theta(n)$ $\Theta(n^2)$ Worst case $\Theta(n^2)$ $\Theta(n^2)$ Space $O(1)$ $O(1)$ Stable? Yes No (swap can reorder equals) Adaptive? Yes No Swaps Up to $\Theta(n^2)$ Exactly $n - 1$ :::

When to reach for each

3.17 Shell Sort

Shell sort is the first sort we meet that breaks out of the quadratic class — not by doing something dramatically new, but by applying insertion sort cleverly in multiple passes over interleaved sublists. It’s the bridge between the simple sorts of 3.15—3.16 and the $O(n \log n)$ sorts of the next chapter. Named for Donald Shell, 1959.

The core insight

Insertion sort is slow on unsorted input because each misplaced element can only move one slot at a time. A tiny value at the end of a big array has to be swapped past every larger neighbor, one pair at a time, to reach the front — that’s the $n^2$ .

Interleaved lists and the “gap”

Gap of 3 on a 9-element list

Array: $[56, 42, 93, 12, 77, 82, 75, 91, 36]$

With gap 3, the three interleaved sublists are:

indices $\{0, 3, 6\}$ : $(56, 12, 75)$
indices $\{1, 4, 7\}$ : $(42, 77, 91)$
indices $\{2, 5, 8\}$ : $(93, 82, 36)$

Each is sorted independently. After sorting the three interleaved lists, the array looks like: $[12, 42, 36, 56, 77, 82, 75, 91, 93]$ .

The array isn’t sorted yet, but it’s close: the three smallest elements all ended up in the first three slots. That’s the setup Shell sort creates so that the final gap-1 pass (plain insertion sort) runs in nearly linear time.

Shell sort in C++

Shell sort implementation

// Insertion sort with a custom step size
static void insertionSortGap(std::vector<int>& nums,
                             std::size_t start,
                             std::size_t gap) {
    for (std::size_t i = start + gap; i < nums.size(); i += gap) {
        std::size_t j = i;
        while (j >= gap && nums[j] < nums[j - gap]) {
            std::swap(nums[j], nums[j - gap]);
            j -= gap;
        }
    }
}

void shellSort(std::vector<int>& nums) {
    for (std::size_t gap = nums.size() / 2; gap > 0; gap /= 2) {
        for (std::size_t start = 0; start < gap; ++start) {
            insertionSortGap(nums, start, gap);
        }
    }
}

The outer loop shrinks the gap (halving here). For each gap, the inner loop runs an insertion-sort variant on each of the $K$ interleaved sublists. The final pass uses gap = 1, which is plain insertion sort.

Choice of gap sequence

::: center Gap sequence Example ( $n=100$ ) Worst-case runtime

Halving: $n/2, n/4, \ldots, 1$ (original Shell) 50, 25, 12, 6, 3, 1 $O(n^2)$ Hibbard: $2^k - 1$ 63, 31, 15, 7, 3, 1 $O(n^{3/2})$ Sedgewick / Knuth 121, 40, 13, 4, 1 $O(n^{4/3})$ Ciura (empirical, best known small- $n$ ) 57, 23, 10, 4, 1 very fast in practice :::

Why this beats plain insertion sort

Properties

::: center Property Shell sort

Best case $O(n \log n)$ (already sorted, depends on sequence) Worst case $O(n^2)$ (naïve halving) down to $O(n^{4/3})$ (Sedgewick) Average case Depends on gap sequence; between $O(n^{5/4})$ and $O(n^{3/2})$ in practice Space $O(1)$ extra — in-place Stable? No Adaptive? Somewhat — fewer passes on presorted input :::

When to use it

3.18 Quicksort

Quicksort is the first algorithm we meet that achieves $O(n \log n)$ on average — and it’s the most widely used comparison sort in practice. Its strategy is a textbook example of divide-and-conquer: do a bit of work to partition the problem into two smaller subproblems, recurse on each, and stitch the result together. Invented by Tony Hoare in 1959 while he was a graduate student trying to sort Russian words for machine translation.

The idea: partition and recurse

The Hoare-style partition

The textbook’s partition is a variant of Hoare’s original. Two index pointers walk from the ends toward each other, swapping out-of-place values when they meet misplaced elements.

Hoare partition in C++

static std::size_t partition(std::vector<int>& nums,
                             std::size_t low,
                             std::size_t high) {
    std::size_t mid = low + (high - low) / 2;
    int pivot = nums[mid];

    while (true) {
        while (nums[low]  < pivot) ++low;
        while (pivot < nums[high]) --high;

        if (low >= high) return high;

        std::swap(nums[low], nums[high]);
        ++low;
        --high;
    }
}

void quicksort(std::vector<int>& nums,
               std::size_t low,
               std::size_t high) {
    if (low >= high) return;                          // base case
    std::size_t mid = partition(nums, low, high);
    quicksort(nums, low, mid);                         // left half
    quicksort(nums, mid + 1, high);                    // right half
}

Pivot picked at the midpoint; two pointers walk inward; swap when both find something on the wrong side; stop when they meet. After the partition returns, each side is recursively sorted.

Runtime: average vs. worst

Pivot selection strategies

::: center Strategy Behavior

First or last element Disastrously $O(n^2)$ on sorted inputs. Don’t. Middle element Good for sorted inputs; still $O(n^2)$ on adversarial data. Random element Expected $O(n \log n)$ no matter the input pattern. Adversary can’t predict the pivot. Median-of-three (first, middle, last) Cheap approximation of the true median; very robust in practice. The choice most real implementations make. Introsort Start with quicksort, but if recursion depth exceeds $2 \log n$ , switch to heap sort. Guaranteed $O(n \log n)$ worst case. std::sort does this. :::

Properties

::: center Property Quicksort

Best case $\Theta(n \log n)$ Average case $\Theta(n \log n)$ Worst case $\Theta(n^2)$ — mitigated by pivot strategy Space $O(\log n)$ recursion stack (in-place for the data) Stable? No — partition swaps non-adjacent elements Adaptive? Not especially — depends on pivot choice :::

Why is it called quick if it can be $O(n^2)$ ?

3.19 Merge Sort

Quicksort gets its $O(n \log n)$ on average and pays a rare $O(n^2)$ on bad pivots. Merge sort buys a guaranteed $O(n \log n)$ worst case plus stability, at the cost of $O(n)$ extra memory. It’s also divide-and-conquer, but with the work distributed differently: quicksort does the work before recursing (partition then recurse), merge sort does the work after (recurse then merge). Invented by John von Neumann in 1945.

The idea: recurse then merge

The merge step

The merge is where everything happens. Two already-sorted subsequences can be combined into one sorted sequence in linear time by walking both with two pointers and always taking the smaller of the two front elements.

Merging two sorted runs in C++

static void merge(std::vector<int>& nums,
                  std::size_t i, std::size_t j, std::size_t k) {
    // nums[i..j]   is the left  (sorted) half
    // nums[j+1..k] is the right (sorted) half
    std::vector<int> merged;
    merged.reserve(k - i + 1);

    std::size_t left = i, right = j + 1;
    while (left <= j && right <= k) {
        if (nums[left] <= nums[right]) {
            merged.push_back(nums[left++]);
        } else {
            merged.push_back(nums[right++]);
        }
    }
    while (left  <= j) merged.push_back(nums[left++]);
    while (right <= k) merged.push_back(nums[right++]);

    for (std::size_t p = 0; p < merged.size(); ++p) {
        nums[i + p] = merged[p];
    }
}

Scan both halves in lockstep. Whichever front element is smaller, take it. When one half is exhausted, flush the other. Finally, copy the merged buffer back to nums[i..k].

Merge sort in C++

The recursive driver

void mergeSort(std::vector<int>& nums,
               std::size_t i, std::size_t k) {
    if (i >= k) return;                             // base case
    std::size_t j = i + (k - i) / 2;                // midpoint
    mergeSort(nums, i, j);                           // sort left
    mergeSort(nums, j + 1, k);                       // sort right
    merge(nums, i, j, k);                            // combine
}

The recursion tree has depth $\log_2 n$ ; each level does $\Theta(n)$ work in its merge calls. Total: $\Theta(n \log n)$ .

Runtime: why always $O(n \log n)$

The Master Theorem: a formal tool for divide-and-conquer

The recursion-tree argument above is one way to solve a recurrence. For the broad class $T(n) = a \cdot T(n/b) + f(n)$ — “solve $a$ subproblems of size $n/b$ , plus do $f(n)$ work to combine them” — there’s a closed-form result called the Master Theorem (CLRS Ch 4 / OCW r03). Three cases, depending on how $f(n)$ compares to $n^{\log_b a}$ (the work that would happen if you only counted the leaves of the recursion tree):

::: center Case When Then $T(n) =$

1. Leaves win $f(n) = O(n^{\log_b a - \varepsilon})$ for some $\varepsilon > 0$ $\Theta(n^{\log_b a})$ 2. Balanced $f(n) = \Theta(n^{\log_b a})$ $\Theta(n^{\log_b a} \log n)$ 3. Root wins $f(n) = \Omega(n^{\log_b a + \varepsilon})$ + regularity $\Theta(f(n))$ :::

Merge sort: $T(n) = 2T(n/2) + \Theta(n)$ . Here $a=2, b=2$ , so $\log_b a = 1$ , and $f(n) = n = \Theta(n^1)$ — case 2 applies. $T(n) = \Theta(n \log n)$ . The hand-derivation above is a worked instance of case 2. The Master Theorem is just the general formula that lets you skip the recursion-tree drawing for any recurrence in this form.

Binary search: $T(n) = T(n/2) + O(1) = 1 \cdot T(n/2) + \Theta(n^0)$ , so $\log_b a = 0$ , $f(n) = \Theta(n^0)$ — case 2 again. $T(n) = \Theta(\log n)$ .

Quicksort (best case): $T(n) = 2T(n/2) + \Theta(n)$ , same as merge sort, so $\Theta(n \log n)$ . (Worst case requires a different recurrence and falls outside the Master Theorem.)

A handful of useful recurrences and their solutions:

::: center

$T(n) = T(n - 1) + O(1)$ $\Theta(n)$ $T(n) = T(n - 1) + O(n)$ $\Theta(n^2)$ $T(n) = T(n/2) + O(1)$ $\Theta(\log n)$ $T(n) = 2T(n/2) + O(1)$ $\Theta(n)$ $T(n) = 2T(n/2) + O(n)$ $\Theta(n \log n)$ $T(n) = 2T(n/2) + O(n \log n)$ $\Theta(n \log^2 n)$ $T(n) = 2T(n - 1) + O(1)$ $\Theta(2^n)$

:::

The full proof of the Master Theorem — including which $f(n)$ shapes fall into which case — is in CLRS Ch 4. For ch_3 the takeaway is that the recursion-tree arguments throughout and are instances of a general result, not one-off clever tricks.

Memory cost

Properties

::: center Property Merge sort

Best case $\Theta(n \log n)$ Average case $\Theta(n \log n)$ Worst case $\Theta(n \log n)$ — guaranteed Space $O(n)$ extra — temporary merge buffer Stable? Yes Adaptive? Not natively (plain merge sort). Variants like Timsort are adaptive. :::

Merge sort vs. quicksort

::: center Criterion Quicksort Merge sort

Best / avg case $\Theta(n \log n)$ $\Theta(n \log n)$ Worst case $\Theta(n^2)$ $\Theta(n \log n)$ Extra memory $O(\log n)$ (stack) $O(n)$ (buffer) Stable? No Yes Cache behavior Excellent (sequential) Good (streaming) In-place? Yes No Recursion depth $O(\log n)$ avg, $O(n)$ worst $O(\log n)$ always :::

Timsort: merge sort’s real-world descendant

3.20 Radix Sort

Every sort we’ve seen so far is comparison-based: it uses < between pairs of elements as its only decision procedure. The lower bound for that class is $\Omega(n \log n)$ . Radix sort is our first non-comparison sort — it never compares two elements to each other — and it breaks the $n \log n$ bound, sorting in $O(n \cdot d)$ where $d$ is the number of digits. For fixed-width integer keys, that’s effectively $O(n)$ .

The trick: sort by one digit at a time

The LSD algorithm

Radix sort in C++, non-negative integers

void radixSort(std::vector<int>& nums) {
    if (nums.empty()) return;

    int maxVal = *std::max_element(nums.begin(), nums.end());
    std::vector<std::vector<int>> buckets(10);

    for (int pow10 = 1; maxVal / pow10 > 0; pow10 *= 10) {
        for (int v : nums) {
            int digit = (v / pow10) % 10;
            buckets[digit].push_back(v);
        }
        std::size_t idx = 0;
        for (auto& bucket : buckets) {
            for (int v : bucket) nums[idx++] = v;
            bucket.clear();
        }
    }
}

Outer loop advances through the digits (ones, tens, hundreds, …). Inner first loop distributes values to buckets; inner second loop gathers them back in order. The pass is stable because we iterate nums in order and push_back preserves arrival order within a bucket.

Tracing a small example

::: center Step Array

Input 170, 45, 75, 90, 802, 24, 2, 66 After 1’s pass 170, 90, 802, 2, 24, 45, 75, 66 After 10’s pass 802, 2, 24, 45, 66, 170, 75, 90 After 100’s pass 2, 24, 45, 66, 75, 90, 170, 802 :::

Three passes, because the max value has three digits. After each pass, the prefix of digit-sorted-ness grows by one.

Runtime

Handling negatives and other bases

Properties

::: center Property Radix sort (LSD)

Time (best / avg / worst) $\Theta(n \cdot d)$ — all cases the same Space $\Theta(n + B)$ where $B$ is the base Stable? Yes — and correctness depends on it Adaptive? No — doesn’t notice already-sorted input Works on? Integer keys (or anything decomposable into fixed-width digits) :::

When to reach for radix sort

Counting sort: the standalone non-comparison sort

Radix sort uses counting sort once per digit. But counting sort is also a complete sorting algorithm in its own right — the right choice when keys are integers in a known small range and you want $O(n + k)$ time, where $k$ is the size of the range.

Counting sort in C++

void countingSort(std::vector<int>& nums, int k) {
    // Assumes every nums[i] satisfies 0 <= nums[i] < k.
    std::vector<int> count(k, 0);
    for (int v : nums)              ++count[v];          // count occurrences
    for (int i = 1; i < k; ++i)     count[i] += count[i-1]; // cumulative
    std::vector<int> out(nums.size());
    for (int i = nums.size() - 1; i >= 0; --i) {         // walk BACKWARD
        out[--count[nums[i]]] = nums[i];
    }
    nums = std::move(out);
}

The cumulative-sum array tells you exactly where each value’s “block” ends in the output. Walking the input backward and decrementing as you go preserves the original order of equal keys — that’s why counting sort is stable.

3.21 Overview of Fast Sorting Algorithms

The last several sections introduced a parade of sorting algorithms. This section steps back and classifies them. Two questions organize the view: how fast? (average-case complexity) and what kind? (does the algorithm compare elements, or does it exploit more structure in the keys?).

The speed classification

::: center Algorithm Average case Fast?

Selection sort $\Theta(n^2)$ No Insertion sort $\Theta(n^2)$ No Shell sort $\Theta(n^{1.5})$ (typical sequences) No Quicksort $\Theta(n \log n)$ Yes Merge sort $\Theta(n \log n)$ Yes Heap sort $\Theta(n \log n)$ Yes Radix sort $\Theta(n \cdot d) = O(n)$ for fixed-width Yes :::

The $\Omega(n \log n)$ lower bound for comparison sorts

Comparison vs. non-comparison sorts

::: center Algorithm Comparison sort?

Selection, insertion, shell sort Yes Quicksort, merge sort, heap sort Yes Radix sort (and counting, bucket sort) No :::

Best / average / worst, side by side

Average case is the headline number, but the other two cases matter when you care about guarantees (worst) or optimized input (best).

::: center Algorithm Best Average Worst

Quicksort $\Theta(n \log n)$ $\Theta(n \log n)$ $\Theta(n^2)$ Merge sort $\Theta(n \log n)$ $\Theta(n \log n)$ $\Theta(n \log n)$ Heap sort $\Theta(n)$ * / $\Theta(n \log n)$ $\Theta(n \log n)$ $\Theta(n \log n)$ Radix sort $\Theta(n)$ $\Theta(n)$ $\Theta(n)$ :::

Picking a fast sort: a mini decision tree

The extended comparison table

Everything from the chapter, in one place:

::: center Algorithm Best Average Worst Space Stable? Adaptive?

Selection $n^2$ $n^2$ $n^2$ $1$ No No Insertion $n$ $n^2$ $n^2$ $1$ Yes Yes Shell $n \log n$ $n^{1.5}$ $n^{1.5\text{--}2}$ $1$ No Some Quicksort $n \log n$ $n \log n$ $n^2$ $\log n$ No No Merge $n \log n$ $n \log n$ $n \log n$ $n$ Yes No Heap $n \log n$ $n \log n$ $n \log n$ $1$ No No Radix $n$ $n$ $n$ $n$ Yes No :::

What this connects to

Forward links to later chapters

Chapter 4 (linked lists). Every performance comparison in ch. 4 is “compared to a vector, …”. The complexity vocabulary from 3.9 and 3.10 is what lets those comparisons land. Linked-list traversal is $O(n)$ because each step is constant and there are $n$ of them — the exact reasoning you practiced here.
Chapter 5 (hash tables). The big claim — “hash lookup is $O(1)$ expected” — only makes sense if you’re fluent with expected vs. worst case, which is a 3.10 skill. The chaining and probing strategies there are extensions of the collision idea introduced at the end of 3.1.
Chapter 6 (BSTs). BST insert/search/remove are $O(h)$ , which is $O(\log n)$ on a balanced tree and $O(n)$ on a degenerate one. The “balanced” piece is literally about whether the tree shape keeps you on the log curve from 3.10’s growth hierarchy.
Sorting choices in later work. Whenever you see std::sort (introspection sort, essentially quicksort + heapsort fallback) you’re looking at the quicksort analysis from 3.18. When you see std::stable_sort, that’s merge sort from 3.19 with its stability guarantee.

Companion materials. Compact notes: chapters/ch_3/notes.tex (includes the full sort comparison table). Practice prompts (problem $\to$ pseudocode $\to$ C++): chapters/ch_3/practice.md.

3.1 Representing Information as Bits

Bits and bytes

Why bits

ASCII: bits that mean characters

A subset of the ASCII table

What ASCII can’t do: everything else

Connecting bits back to data structures

3.2 Data Structures

The seven structures you’ll meet this semester

Why there are so many

A concrete example: the shift problem

How to pick a data structure

The C++ standard library’s version of this list

3.3 Relation Between Data Structures and Algorithms

Direction 1: Different structure, different algorithm

Direction 2: Algorithms use structures as scratch space

Putting the two directions together

3.4 Abstract Data Types

Why the separation matters

The standard ADTs you should recognize

C++ makes the ADT/structure distinction concrete

Using ADTs to keep caller code honest

3.5 Applications of ADTs

Abstraction as a productivity lever

ADTs in standard libraries

Why CS 300 still has you build them by hand

Choosing the right ADT is the actual skill

3.6 Searching and Algorithm Runtime

Linear search

Why linear — and when it’s fine

Runtime as a function of input size

Ignoring constants: why we say “on the order of NNN”

Searching, structures, and algorithms together

3.8 Binary Search

The idea

Binary search in C++

Why O(log⁡n)O(\log n)O(logn)

The bigger lesson

3.9 Constant-Time Operations

What counts as constant time

Why fixed size matters

Counting the right things

The rule of thumb

3.10 Growth of Functions and Complexity

Best case, worst case, and T(N)T(N)T(N)

Upper and lower bounds

Asymptotic notation: strip the constants

How to read a big-O claim

The growth-rate hierarchy

In practice

3.14 Sorting: Introduction

Why sorting is its own field

The fundamental constraint

What makes sorts differ

In C++

3.15 Insertion Sort

The idea

Insertion sort in C++

Worst-case analysis: O(n2)O(n^2)O(n2)

Best case: O(n)O(n)O(n) on already-sorted input

Why this matters in practice

Properties

3.16 Selection Sort

Selection sort in C++

Why it always does Θ(n2)\Theta(n^2)Θ(n2) comparisons

Where selection sort is better than insertion sort

When to reach for each

3.17 Shell Sort

The core insight

Interleaved lists and the “gap”

Shell sort in C++

Choice of gap sequence

Why this beats plain insertion sort

Properties

When to use it

3.18 Quicksort

The idea: partition and recurse

The Hoare-style partition

Runtime: average vs. worst

Pivot selection strategies

Ignoring constants: why we say “on the order of $N$ ”

Why $O(\log n)$

Best case, worst case, and $T(N)$

Worst-case analysis: $O(n^2)$

Best case: $O(n)$ on already-sorted input

Why it always does $\Theta(n^2)$ comparisons

Why is it called quick if it can be $O(n^2)$ ?

Runtime: why always $O(n \log n)$

The $\Omega(n \log n)$ lower bound for comparison sorts