13.0 The comparison-sort lower bound

Before walking specific sorts, we derive the bound that constrains every comparison-based sort: no comparison sort can do better than $\Omega(n \log n)$ comparisons in the worst case. This is not a property of any one algorithm --- it is a property of the comparison-sort model, and it is what motivates the non-comparison sorts (counting / radix / bucket) in §13.6 and §13.7.

The decision-tree model

The decision-tree model captures any comparison sort: insertion, selection, merge, quicksort, heapsort, Timsort, introsort, pdqsort. Each algorithm corresponds to a different shape of tree, but every algorithm in the family is one tree.

The bound

The proof is short. Stirling’s approximation gives $n! \geq (n/e)^n$, so $\log_2(n!) \geq n \log_2 n - n \log_2 e \geq \tfrac{1}{2} n \log_2 n$ for all $n \geq 4$. The decision-tree height bound transfers directly to a worst-case-comparisons bound, and worst-case comparisons bound the worst-case running time from below.

The 3-element decision tree

The smallest non-trivial example: $n = 3$. There are $3! = 6$ permutations, so the tree must have at least 6 leaves, and a binary tree with 6 leaves has height at least $\lceil \log_2 6 \rceil = 3$. The optimal sort for $n = 3$ uses exactly 3 comparisons in the worst case --- and the tree below is essentially what insertion sort on 3 elements builds.

::: center :::

The leaves are the 6 permutations of $\{a, b, c\}$. The tree has height 3, matching $\lceil \log_2 6 \rceil$. No 3-element comparison sort can do better in the worst case: any tree with fewer than 6 leaves would alias two distinct permutations and be incorrect.

Comparison vs. non-comparison sorts

13.1 Bubble Sort

The algorithm

void bubbleSort(std::vector<int>& a) {
    int n = a.size();
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            if (a[j] > a[j + 1])
                std::swap(a[j], a[j + 1]);
        }
    }
}

The inner loop shrinks each pass because the last $i$ elements are already in their final position.

Cost

• Best case (already sorted): still $O(n^2)$ comparisons in the plain version. An optimization: short-circuit when an entire pass made no swaps, giving $O(n)$ best case.

• Average: $O(n^2)$.

• Worst case (reverse sorted): $O(n^2)$ comparisons, $O(n^2)$ swaps.

• Space: $O(1)$.

• Stable: yes (equal elements never swap past each other).

Why you’ll never use bubble sort

What bubble sort is good for

• Teaching the concept of an in-place comparison sort.

• Interview questions about algorithmic complexity.

• Tiny inputs ($n \leq 20$) where the constant factor is irrelevant.

• Hardware sorting networks, where adjacent-pair compare-and-swap is the primitive operation.

13.2 Quickselect

The problem

The naive solution: sort, return a[k]. That’s $O(n \log n)$. Quickselect does it in $O(n)$ average time without fully sorting.

The insight

Quickselect borrows Quicksort’s partition routine — the one that picks a pivot, puts smaller elements to the left, larger to the right, and returns the pivot’s final position.

Algorithm

int partition(std::vector<int>& a, int lo, int hi) {
    int pivot = a[(lo + hi) / 2];
    int i = lo - 1, j = hi + 1;
    while (true) {
        do { ++i; } while (a[i] < pivot);
        do { --j; } while (a[j] > pivot);
        if (i >= j) return j;
        std::swap(a[i], a[j]);
    }
}

int quickselect(std::vector<int>& a, int lo, int hi, int k) {
    if (lo >= hi) return a[lo];
    int p = partition(a, lo, hi);
    if (k <= p) return quickselect(a, lo, p, k);
    return quickselect(a, p + 1, hi, k);
}

Cost

• Average: $O(n)$. Partition costs $n$; the next recursion is on $n/2$; then $n/4$; …total $n + n/2 + n/4 + \ldots = O(n)$ by geometric sum.

• Worst: $O(n^2)$, same as naive quicksort, when pivots are consistently bad.

• Median-of-medians gives $O(n)$ worst-case selection, but the constant is large; in practice quickselect with a random or median-of-three pivot is faster.

Median-of-medians for worst-case O(n) selection

The median-of-medians algorithm (Blum, Floyd, Pratt, Rivest, Tarjan, 1973; CLRS §9.3) gives worst-case $O(n)$ selection by computing a pivot guaranteed to be “good enough” on every input. The construction:

1. Split the input into $\lceil n / 5 \rceil$ groups of 5 consecutive elements (the last group may have fewer than 5).

2. Sort each group in $O(1)$ time (5 elements: at most 7 comparisons by an optimal 5-element sorting network). The middle of each sorted group is that group’s median.

3. Recursively call median-of-medians on the collected $\lceil n/5 \rceil$ group-medians to find their median --- call it $M$.

4. Use $M$ as the pivot for the standard quickselect partition step.

The pivot $M$ is greater than at least $3 \lceil n/10 \rceil - 6$ elements and less than at least $3 \lceil n/10 \rceil - 6$ elements (each of the $\lceil n/10 \rceil$ groups whose median is below $M$ contributes at least 3 elements below $M$). This guarantees that every recursive call shrinks the problem by at least a $7/10$ factor in the worst case. The recurrence $T(n) \le T(n/5) + T(7n/10) + O(n)$ solves to $T(n) = O(n)$ because $1/5 + 7/10 = 9/10 < 1$.

C++ standard library

You don’t have to write quickselect yourself — C++ gives it to you:

#include <algorithm>
// Rearranges [begin, end) so nth is the element that would be at
// position n in a fully sorted range. Everything before nth is <=,
// everything after is >=. Average O(n).
std::nth_element(a.begin(), a.begin() + k, a.end());
int kthSmallest = a[k];

Applications

• Median / percentile computation.

• Top-$k$ queries. After nth_element, the first $k$ entries are the top-$k$ (unsorted). If you need them sorted, sort just that prefix.

• Machine learning: quickselect-based k-nearest-neighbor scoring.

• Streaming statistics: approximate quantiles via repeated quickselect.

13.3 Bucket Sort

The idea

This is a non-comparison sort — it exploits numerical structure of the values to beat the $\Omega(n \log n)$ comparison-sort lower bound (§13.0).

Algorithm

Given non-negative numbers up to some max value $M$:

1. Create $K$ buckets. Bucket $i$ holds values in $[i \cdot M/K, (i+1) \cdot M/K)$.

2. For each element $x$, compute bucket = floor(x * K / (M + 1)) and append $x$ to that bucket.

3. Sort each bucket (insertion sort or any other; each bucket is small).

4. Concatenate buckets in order.

void bucketSort(std::vector<int>& a, int K) {
    if (a.empty()) return;
    int maxV = *std::max_element(a.begin(), a.end());
    std::vector<std::vector<int>> buckets(K);

    for (int x : a) {
        int idx = (long long)x * K / (maxV + 1);
        buckets[idx].push_back(x);
    }

    a.clear();
    for (auto& b : buckets) {
        std::sort(b.begin(), b.end());
        a.insert(a.end(), b.begin(), b.end());
    }
}

Cost

Let $n$ be the array size and $K$ the bucket count.

• Distribution pass: $O(n)$.

• Per-bucket sort: if values are uniform, each bucket has $\approx n/K$ elements. Sorting each with $O(m^2)$ insertion sort gives total $K \cdot (n/K)^2 = n^2/K$. With $K = n$, this is $O(n)$.

• Concatenate: $O(n + K)$.

• Total (uniform distribution, $K = n$): $O(n)$.

• Worst case (all elements in one bucket): $O(n^2)$.

Related algorithms

• Counting sort: degenerate bucket sort where each bucket holds exactly one value. $O(n + M)$ time, $O(M)$ space. Perfect for small-range integers. Full treatment in §13.6.

• Radix sort: iterate counting sort on each digit. $O(d(n + b))$ for $d$-digit numbers in base $b$. Used in database sorts, GPU sorts, and networking. Full treatment in §13.7.

• Pigeonhole sort: counting sort by another name, when value range $=$ number of elements.

13.4 List Data Structure

The idiom

A linked list (ch. 4) can be represented in two ways:

• Just a head pointer (and maybe a tail pointer), held in local variables or as member fields.

• A wrapper container — a List struct that owns head, tail, and maybe size. Functions take a List* instead of a raw head pointer.

// Approach 1: just nodes.
struct Node { int data; Node* next; };
Node* head = nullptr;
Node* tail = nullptr;
int size = 0;

// Approach 2: list wrapper.
struct List {
    Node* head = nullptr;
    Node* tail = nullptr;
    int size = 0;
};

void listPushBack(List* lst, int data) {
    Node* n = new Node{data, nullptr};
    if (!lst->head) lst->head = n;
    else            lst->tail->next = n;
    lst->tail = n;
    ++lst->size;
}

Why wrap?

::: center Operation Head-only list Wrapped list

Insert at head $O(1)$ $O(1)$ Insert at tail $O(n)$ (walk to end) $O(1)$ (tail ptr) Get size $O(n)$ or maintained externally $O(1)$ (cached) Pass to function 3 args (head, tail, size) 1 arg (List*) :::

Why not just use std::list?

When linked lists are the wrong answer

Even with a nice wrapper, linked lists are frequently worse than std::vector (dynamic array):

• Cache locality: array elements are contiguous, list nodes scattered across the heap.

• Memory overhead: each node has a next pointer, often doubling memory vs. raw values.

• Random access: $O(n)$ for list, $O(1)$ for array.

• Iteration: much slower on a list due to cache misses on every next.

Use a linked list when you need cheap insertion/deletion at interior points with existing iterators, or when you’re building something that requires pointer stability (e.g., an LRU cache with external references). Otherwise, default to std::vector.

13.5 Circular Lists

The definition

// Singly-linked circular
struct Node { int data; Node* next; };
// Last node's next points back to head.

// Doubly-linked circular (most common in practice)
struct DNode { int data; DNode* prev; DNode* next; };
// Last node's next -> head; head's prev -> last node.

Traversal

The key trick: stop when you come back to the start, not when you hit nullptr.

void traverseCircular(Node* head) {
    if (!head) return;
    Node* cur = head;
    do {
        visit(cur);
        cur = cur->next;
    } while (cur != head);
}

Why circular lists exist

• Round-robin scheduling. OS schedulers cycle through ready processes; each yield pops one and reappends it at the end. A circular list gives O(1) “next process” and O(1) append.

• Music players on “repeat all.” Queue is a circular list of tracks.

• Ring buffers (logically circular, though usually array-based for cache locality).

• Josephus problem and other classic cyclic-elimination algorithms — naturally circular.

• Token-passing networks. Token Ring Ethernet was literally a circular list of nodes; each station had one successor.

• Doubly-linked circular lists with a sentinel give branch-free insert/delete at any position.

Sentinel trick for doubly-linked circular lists

A sentinel node — a dummy that’s never “real” data but completes the circle — removes the “is this node the head / tail” special cases:

struct DNode { int data; DNode* prev; DNode* next; };

struct CircularList {
    DNode sentinel;   // sentinel.next = head, sentinel.prev = tail
    CircularList() { sentinel.prev = sentinel.next = &sentinel; }
};

// Insert n before 'where' -- no null checks needed.
void insertBefore(DNode* where, DNode* n) {
    n->next = where;
    n->prev = where->prev;
    where->prev->next = n;
    where->prev = n;
}

// Remove n -- no null checks needed.
void remove(DNode* n) {
    n->prev->next = n->next;
    n->next->prev = n->prev;
}

::: center :::

The sentinel is always present, even when the list is logically empty (then sentinel.next == sentinel.prev == &sentinel). There is no “head == nullptr” branch in insertBefore / remove --- the sentinel guarantees both prev and next are non-null for every real node, and operations on the sentinel itself are well-defined.

Traversal in reverse (doubly-linked)

Mirror of the forward case — walk prev pointers from any starting point until you return:

void traverseReverseCircular(DNode* tail) {
    if (!tail) return;
    DNode* cur = tail;
    do {
        visit(cur);
        cur = cur->prev;
    } while (cur != tail);
}

13.6 Counting sort

The idea

Counting sort sidesteps the comparison-sort lower bound of §13.0 by treating each key as an array index rather than as something to compare. The price: it only works when keys are non-negative integers in a known small-ish range.

Algorithm

Given input $A[0 \dots n-1]$ with each $A[i] \in [0, k)$:

1. Count. Allocate $C[0 \dots k-1]$ initialised to zero. Scan $A$ once; for each $A[i]$, increment $C[A[i]]$. Now $C[v]$ is the number of input elements equal to $v$.

2. Prefix sum. Replace $C$ with its running sum: $C[v] \leftarrow C[v] + C[v-1]$ for $v$ from 1 to $k-1$. Now $C[v]$ is the number of input elements $\le v$, which is also one past the last position where a $v$ should land in the output.

3. Place. Allocate output $B[0 \dots n-1]$. Iterate $i$ from $n-1$ down to $0$ (right-to-left for stability); for each $A[i]$, set $C[A[i]] \leftarrow C[A[i]] - 1$, then $B[C[A[i]]] \leftarrow A[i]$.

// Stable counting sort. Keys must satisfy 0 <= a[i] < k.
void countingSort(std::vector<int>& a, int k) {
    int n = a.size();
    if (n == 0) return;
    std::vector<int> C(k, 0);
    std::vector<int> B(n);

    // 1. Count.
    for (int i = 0; i < n; ++i) ++C[a[i]];

    // 2. Prefix sum: C[v] = number of inputs <= v.
    for (int v = 1; v < k; ++v) C[v] += C[v - 1];

    // 3. Place right-to-left for stability.
    for (int i = n - 1; i >= 0; --i) {
        --C[a[i]];
        B[C[a[i]]] = a[i];
    }

    a = std::move(B);
}

Cost

• Time: $O(n + k)$. Three linear scans of size $n$, $k$, $n$.

• Space: $O(n + k)$. The count array $C$ has size $k$; the output array $B$ has size $n$.

• Stable: yes. The right-to-left placement guarantees that two equal elements preserve their input order. (Going left-to-right would reverse them --- this is the most common counting-sort bug.)

• In-place: no. Counting sort needs $O(n + k)$ auxiliary space.

Stability proof

Claim. Counting sort with right-to-left placement is stable: for $i < j$ with $A[i] = A[j]$, the output places $A[i]$ before $A[j]$.

Proof sketch. The right-to-left placement loop processes $A[j]$ first (since $j > i$), decrements $C[A[j]]$, and writes $A[j]$ to position $C[A[j]]$. When the loop later reaches $A[i]$, $C[A[i]]$ has been decremented at least once (by the $A[j]$ write), so $A[i]$ writes to a smaller index --- i.e. to the left of $A[j]$ in the output. Stability holds for any equal-key pair.

Worked layout: counting array \to output

::: center :::

The picture above sorts $A = [2, 5, 3, 0, 2, 3, 0, 3]$ in three phases: the count vector $C$ tallies each key value (top: two 0s, no 1s, two 2s, three 3s, no 4s, one 5); the prefix sum ($C \leftarrow$ running sum) gives the position one past where each key class ends in $B$; the right-to-left placement step walks the input backward and stamps each element into its final slot, decrementing $C$ as it goes.

Use cases

• Pre-pass for radix sort. Each digit pass of radix sort is a counting sort on $k = b$ (the radix). §13.7 fully exploits this.

• Integer histograms in image processing. Pixel intensities are 8-bit ($k = 256$); a counting-sort “count” phase is the histogram, and the prefix-sum phase is the cumulative distribution function used in histogram equalisation.

• Database aggregations. GROUP BY on a low-cardinality column (e.g. enum / boolean / status) is a counting sort: bucketise rows by group key in one pass.

• Bucket sort sub-step. When per-bucket sort in §13.3 turns out to be on a small key universe, counting sort is what to reach for.

13.7 Radix sort

The idea

Radix sort beats the comparison-sort lower bound when keys are fixed-width: $O(d(n + b)) = O(n)$ if $d$ and $b$ are both constants. For 32-bit integers with $b = 256$ ($d = 4$ byte passes), that gives roughly $4 \cdot (n + 256) = O(n)$ work --- which is why radix sort is the standard parallel sort on GPUs and the go-to integer sort in production analytics engines.

LSD algorithm

The crucial property: each digit pass must be a stable sort, and counting sort is stable by construction (§13.6). So:

1. For digit position $p = 0, 1, \dots, d-1$ (from least-significant to most-significant):

   1. Stable-counting-sort the array on the value of digit $p$ (i.e. $\lfloor x / b^p \rfloor \bmod b$ as the key for input $x$).

2. After $d$ passes, the array is fully sorted.

// LSD radix sort over non-negative integers in base b.
// d is the number of base-b digits sufficient to represent
// every input element.
void radixSortLSD(std::vector<int>& a, int b, int d) {
    int n = a.size();
    if (n == 0) return;
    std::vector<int> B(n);
    long long base = 1;  // = b^p

    for (int p = 0; p < d; ++p) {
        std::vector<int> C(b, 0);

        // Count digit-p occurrences.
        for (int i = 0; i < n; ++i) {
            int digit = (a[i] / base) % b;
            ++C[digit];
        }
        // Prefix sum.
        for (int v = 1; v < b; ++v) C[v] += C[v - 1];
        // Stable placement, right-to-left.
        for (int i = n - 1; i >= 0; --i) {
            int digit = (a[i] / base) % b;
            --C[digit];
            B[C[digit]] = a[i];
        }
        std::swap(a, B);
        base *= b;
    }
}

Cost

• Time: $O(d(n + b))$. Each of the $d$ digit passes is a counting sort with parameters $n$ and $b$.

• Space: $O(n + b)$. One output buffer of size $n$ plus one count buffer of size $b$, reused across passes.

• Stable: yes. Stability of each digit pass is required for correctness.

• In-place: no, in the LSD form. (MSD variants can be made closer to in-place at the cost of recursion overhead.)

Base-vs-passes tradeoff

LSD passes on [170, 45, 75, 90, 802, 24, 2, 66]

::: center :::

MSD radix sort and variable-length keys

LSD radix sort requires every key to have the same number of digits (or be left-padded with zeros). For variable-length keys (strings of different lengths, IP addresses with optional prefixes, etc.) the natural variant is MSD radix sort: process digits from most-significant to least-significant, recursing into each non-empty bucket.

• Algorithm. Bucket the input by the most-significant digit. Recursively radix-sort each non-empty bucket on the next digit. Concatenate buckets in MSD order.

• Strings. MSD radix on strings is the standard string-sort: bucket by first character, recurse on remaining suffix. The recursion bottoms out when a bucket has $\le 1$ string (already sorted) or when the suffix is empty.

• When MSD beats LSD. Variable-length keys (LSD would need padding); early-termination when most strings differ in their first few characters; cache locality (each MSD bucket fits in cache).

• When LSD beats MSD. Fixed-width keys (no recursion overhead); simpler code; no stack-depth bound.

Use cases

• GPU sorts. Radix sort is the canonical parallel sort on GPUs (CUB, Thrust, NVIDIA’s cub::DeviceRadixSort). The pattern is fully data-parallel: each digit pass is a histogram + prefix-scan + scatter, all with well-known GPU primitives.

• Database engine sorts. PostgreSQL’s ORDER BY on integer / fixed-width keys; BigQuery / Snowflake / DuckDB column-store sorts.

• Spotify / streaming-recommendation pipelines. Sort-by-user-id or sort-by-track-id at the petabyte scale uses radix because integer key universes are natural and the parallelism is trivial.

• Network packet processing. Sort by source IP / destination IP / 5-tuple flow key is a fixed-width radix sort, used in DPDK and packet-capture pipelines.

13.8 Production hybrid sorts

The lower bound of §13.0 says no comparison sort beats $O(n \log n)$ in the worst case. But real data is not the worst case --- it has structure (already-sorted runs, nearly-sorted prefixes, repeated keys, small slices), and the performance constants vary by an order of magnitude across algorithms (cache behaviour, branch prediction, allocator behaviour). Every modern standard library ships a hybrid sort: a primary algorithm (quicksort variant), a fallback for adversarial inputs, and a small-array fast-path. This section covers the four most-deployed hybrids.

Introsort

• Why the heapsort fallback. Vanilla quicksort degrades to $O(n^2)$ on adversarial inputs (already sorted, all equal keys with a naive pivot). Heapsort (ch. 7) is $O(n \log n)$ worst case and in-place; the $2 \log_2 n$ recursion-depth threshold ensures the fallback triggers before quicksort does too much damage.

• Why the insertion-sort fast-path. Insertion sort is $O(n^2)$ asymptotically but has a small constant and is cache-friendly; for small ranges ($n \le 16$ or so) it is empirically faster than quicksort due to lower per-call overhead.

• Where it lives. std::sort in libstdc++ (GCC), libc++ (LLVM), and MSVC --- the industry-default C++ general-purpose sort.

Timsort

• Run detection. A single forward scan identifies maximal monotone runs (descending runs are reversed in place to make them ascending). Short runs are extended by insertion sort to a minimum length (typically 32—64) so the merge phase has bounded run count.

• Run-stack merging. Runs are merged in a stack-based discipline that maintains an invariant on the run-length sequence (each run is either at least twice the next or at most equal --- this caps the merge depth at $O(\log n)$).

• Galloping merge. When one run dominates the other (one source feeds many consecutive output elements), the merge switches from element-wise compare to exponential-search, dropping per-element cost from $O(\log n)$ to $O(\log k)$ where $k$ is the run-of-wins length.

• Where it lives. Python list.sort / sorted (since 2.3, 2002); Java Arrays.sort for objects (since Java 7, 2011); Java Collections.sort; Rust’s stable sort (Timsort variant); Android, V8.

Dual-pivot quicksort (dpqsort)

• Pivot selection. Sample 5 elements from the partition (positions $\lfloor n/7 \rfloor, \lfloor 2n/7 \rfloor, \lfloor n/2 \rfloor, \lfloor 5n/7 \rfloor, \lfloor 6n/7 \rfloor$); use the 2nd and 4th in sorted order as $p_1, p_2$.

• Three-way partition. Single pass with three pointers; the equal-to-pivot middle region needs no recursion when the pivots happen to equal.

• Where it lives. Java Arrays.sort for primitive types (int[], long[], etc., since Java 7, 2011). Java’s two-track sort policy (Timsort for objects, dpqsort for primitives) reflects the different optimisation surface: object sorts dominated by comparison cost, primitive sorts dominated by cache and branching.

Pdqsort

• BlockQuicksort partition. Partition with a small lookup buffer to eliminate branches on the element-pivot comparison. Roughly 2$\times$ faster than branched partition on random data.

• Pattern defeat. Adversarial inputs that cause vanilla quicksort to degrade are detected within $O(\log n)$ recursion levels, and the algorithm switches to merge sort (still $O(n \log n)$ but immune to the pathological case).

• Where it lives. Rust’s sort_unstable (since 1.20, 2017); Boost.Sort pdqsort; cppsort library; some libc++ implementations of std::sort.

Language \to default-sort decision

::: center Language / API Default sort Underlying algorithm Stable?

C++ std::sort introsort qsort + heap + insertion no C++ std::stable_sort merge sort merge yes Python list.sort Timsort merge + insertion + run scan yes Java Arrays.sort(Object[]) Timsort merge + insertion + run scan yes Java Arrays.sort(int[]) dpqsort dual-pivot quicksort no Rust sort_unstable pdqsort qsort + block-partition + heap no Rust sort Timsort variant merge + insertion + run scan yes Go sort.Sort introsort qsort + heap + insertion no Go sort.Stable merge sort merge yes :::

13.9 Sort algorithm decision table

The master table for picking a sort given problem properties. Each row is a problem characteristic; each cell is the recommended sort with complexity and a chapter pointer.

::: center Problem profile Recommended sort Cost

Tiny array, $n \le 20$ insertion sort (ch. 3) $O(n^2)$ acceptable Random data, in-place, fast introsort (std::sort) $O(n \log n)$ Random data, stable required Timsort or merge sort $O(n \log n)$ Nearly-sorted input Timsort or insertion sort (ch. 3) $O(n)$ best case Bounded integer keys, $k = O(n)$ counting sort (§13.6) $O(n + k)$ Fixed-width integer keys, large radix sort LSD (§13.7) $O(d(n + b))$ Variable-length string keys MSD radix sort (§13.7) $O(d(n + b))$ Uniform-real distribution, $[0,1)$ bucket sort (§13.3) $O(n)$ expected Find $k$-th element only quickselect (§13.2) $O(n)$ avg Stable sort + adversarial input ok merge sort (ch. 3) $O(n \log n)$ Worst-case bound on sort heapsort (ch. 7) or introsort $O(n \log n)$ No extra memory allowed introsort or heapsort (ch. 7) $O(n \log n)$ GPU / massively parallel radix sort LSD on GPU $O(d \cdot n / p)$ Data does not fit in RAM external merge sort (post-cs-300) $O(n \log n)$ I/O Java primitive array dpqsort (§13.8) $O(n \log n)$ Rust [T]::sort_unstable pdqsort (§13.8) $O(n \log n)$ :::

13.10 Algorithmic list idioms

ch. 4 introduced linked lists as a structure; §13.4 and §13.5 covered the wrapping idiom and circular variant. This section covers the canonical algorithms that operate on linked lists --- the cycle-detection, reversal, merge, and pointer-tricks patterns that underlie a large fraction of production list code and interview questions. All five live at $O(n)$ time and $O(1)$ extra space; the idioms are about how to achieve those bounds.

Floyd’s tortoise-and-hare cycle detection

Why it works. If a cycle exists with $\mu$ pre-cycle nodes (the tail) and $\lambda$ cycle-length, then once both pointers are inside the cycle (after at most $\mu$ steps), the fast pointer gains 1 modulo $\lambda$ per step on the slow pointer, and they meet within $\lambda$ steps.

struct Node { int data; Node* next; };

bool hasCycle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

Cycle length. Once slow == fast, fix slow and advance fast one step per iteration until they meet again; the number of steps is $\lambda$.

int cycleLength(Node* meeting) {
    int len = 1;
    Node* p = meeting->next;
    while (p != meeting) { p = p->next; ++len; }
    return len;
}

Cycle start. After the meeting, reset one pointer to head and advance both at speed 1; they meet at the cycle entry. (Why: at the meeting, slow has travelled $\mu + s$ for some $s < \lambda$ inside the cycle; fast has travelled $2(\mu + s)$. Their offset modulo $\lambda$ is $\mu \bmod \lambda$, so a pointer starting at head and advancing $\mu$ steps lands at the cycle entry --- exactly where slow also lands when the head-pointer catches up.)

Node* cycleStart(Node* head, Node* meeting) {
    Node* p = head;
    Node* q = meeting;
    while (p != q) { p = p->next; q = q->next; }
    return p;
}

In-place list reversal

Reverse a singly-linked list in-place in $O(n)$ time and $O(1)$ extra space. The key trick: maintain three pointers (prev, cur, next) and rewire each node in turn.

// Iterative reversal -- O(n) time, O(1) space.
Node* reverse(Node* head) {
    Node* prev = nullptr;
    Node* cur  = head;
    while (cur) {
        Node* next = cur->next;  // save before clobbering
        cur->next  = prev;
        prev       = cur;
        cur        = next;
    }
    return prev;  // new head
}

// Recursive reversal -- O(n) time, O(n) stack.
Node* reverseRecursive(Node* head) {
    if (!head || !head->next) return head;
    Node* newHead = reverseRecursive(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

The iterative form is preferred in production: same big-$O$, no stack-overflow risk on long lists. The recursive form is elegant for interviews.

Sorted merge of two sorted lists

The merge step from merge sort (ch. 3), but on linked-list representation. $O(n + m)$ time, $O(1)$ extra space (no allocations --- splice nodes in-place).

// Merge two sorted lists into one sorted list.
// Uses a dummy head to simplify the empty-output case.
Node* mergeSorted(Node* a, Node* b) {
    Node dummy{0, nullptr};
    Node* tail = &dummy;
    while (a && b) {
        if (a->data <= b->data) {
            tail->next = a; a = a->next;
        } else {
            tail->next = b; b = b->next;
        }
        tail = tail->next;
    }
    tail->next = a ? a : b;
    return dummy.next;
}

Nth-from-end (two-pointer)

Find the $N$th-from-last node of a singly-linked list in a single pass, $O(n)$ time, $O(1)$ space. Trick: advance a lead pointer $N$ steps ahead, then advance both pointers in lockstep until lead hits nullptr; the trailing pointer is at the $N$th-from-last.

// Returns the Nth-from-last node, or nullptr if list has < N nodes.
Node* nthFromEnd(Node* head, int N) {
    Node* lead = head;
    for (int i = 0; i < N; ++i) {
        if (!lead) return nullptr;  // list shorter than N
        lead = lead->next;
    }
    Node* trail = head;
    while (lead) {
        lead  = lead->next;
        trail = trail->next;
    }
    return trail;
}

The same pattern --- two pointers separated by a fixed gap --- underlies Floyd’s cycle detection (gap $= 1$ but with different speeds), the sliding-window string algorithms, and the “mark-then-find” linked-list patterns generally.

Detecting intersection of two singly-linked lists

Two non-circular singly-linked lists may share a common suffix (a Y-shape). Detect the intersection node in $O(n + m)$ time and $O(1)$ space.

Algorithm 1: length-difference. Walk both lists to measure their lengths. Advance the longer one by $|\text{len}(A) - \text{len}(B)|$ steps. Then advance both in lockstep; the first node where the two pointers coincide is the intersection (or both reach nullptr, meaning no intersection).

int listLength(Node* head) {
    int n = 0;
    while (head) { ++n; head = head->next; }
    return n;
}

Node* intersect(Node* a, Node* b) {
    int la = listLength(a), lb = listLength(b);
    while (la > lb) { a = a->next; --la; }
    while (lb > la) { b = b->next; --lb; }
    while (a && b && a != b) { a = a->next; b = b->next; }
    return (a == b) ? a : nullptr;  // a==b==nullptr => no intersection
}

Algorithm 2: simultaneous-advance with switch. A slicker variant: advance both pointers; when one hits nullptr, restart it at the other list’s head. After at most $\text{len}(A) + \text{len}(B)$ steps, the two pointers either meet at the intersection or both reach nullptr. The trick aligns the two pointers at distance $|\text{len}(A) - \text{len}(B)|$ implicitly via the swap.

13.11 Production references and further reading