The Atlas of Algorithms

Insertion Sort

Build a sorted prefix one element at a time, sliding each new value back into its place — the way most people sort a hand of cards.

O(n²)

Selection Sort

Repeatedly find the smallest remaining value and move it to the front — the fewest swaps any sort can make.

Θ(n²)

Bubble Sort

Sweep through the list swapping out-of-order neighbors; the largest value "bubbles" to the end each pass.

O(n²)

Merge Sort

Split into runs, then merge sorted runs into longer sorted runs — guaranteed n log n, and stable.

Θ(n log n)

O(n) average, O(n²) worst

Quicksort

Pick a pivot, shove everything smaller to its left and larger to its right, then recurse — fast on average, in place.

Θ(n log n) avg

Searching & Selection 2

Searching & Selection

Binary Search

Halve a sorted array each step: compare the middle, then throw away the half that cannot contain the target.

Θ(log n)

Searching & Selection

Quickselect

Find the k-th smallest value without fully sorting — partition, then chase rank k into one side only.

Graphs 4

Breadth-First Search

Flood a grid in expanding waves; the first time the wave touches a cell, it has arrived by a shortest path.

O(V + E)

Dijkstra’s Algorithm

Find the cheapest route through weighted terrain by always settling the nearest unfinished node next.

O((V+E) log V)

A* Search

Dijkstra with a sense of direction: a heuristic pulls the search toward the goal, so it settles a fraction of the cells.

O((V+E) log V)

Kruskal's MST

Connect everything for the least total weight — add the cheapest edge that never makes a cycle.

O(E log E)

Trees & Structures 2

Trees & Structures

Binary Heap

A tree packed into an array that always serves the smallest item next — the engine inside a priority queue.

O(log n) per op

Trees & Structures

Union–Find

Track a growing collection of disjoint sets and merge them in nearly constant time — the backbone of connectivity.

O(α(n)) amortized

Strings 2

Strings

Knuth–Morris–Pratt

Find a pattern in text in linear time by never re-reading a character — a precomputed failure table says how far to jump.

O(n + m)

Strings

Boyer–Moore

Search by comparing the pattern back-to-front and skipping ahead — often examining only a fraction of the text.

O(n/m) best, O(nm) worst

Computational Geometry 2

Computational Geometry

Convex Hull

Snap a rubber band around a cloud of points — the smallest convex polygon that contains them all.

Computational Geometry

Closest Pair of Points

Find the two nearest points among many in O(n log n) — divide the plane, then mind only a thin strip.

Numerical & Number-Theoretic

Numerical & Number-Theoretic 3

Sieve of Eratosthenes

Find every prime up to n by crossing out the multiples of each prime in turn — what survives is prime.

O(n log log n)

Numerical & Number-Theoretic

Euclidean Algorithm

Find the greatest common divisor by repeatedly replacing the larger number with its remainder — the oldest algorithm.

O(log min(a,b))

Numerical & Number-Theoretic

Fast Fourier Transform

Turn a signal into its frequencies in O(n log n) — the divide-and-conquer that reshaped signal processing.

Dynamic Programming & Optimization

Dynamic Programming & Optimization 2

Edit Distance

The fewest insert/delete/substitute edits to turn one string into another — built up from a grid of subproblems.

O(m·n)

Dynamic Programming & Optimization

0/1 Knapsack

Pack the most valuable subset that fits — by solving every smaller capacity for every prefix of items.

O(n·W)

Randomized & Probabilistic 2

Randomized & Probabilistic

Fisher–Yates Shuffle

Shuffle a deck so every ordering is equally likely — one pass, one swap per card, no bias.

O(n)

Randomized & Probabilistic

Skip List

Balanced search without the balancing — random express lanes give expected O(log n) with a coin flip.

O(log n) expected

Compression & Coding 2

Compression & Coding

Huffman Coding

Give frequent symbols short codes and rare ones long codes — the optimal prefix-free code, built by merging the two rarest.

Compression & Coding

LZ77

Compress by pointing back at what you have already seen — the sliding-window idea behind gzip and PNG.

O(n · window)

The Modern & Advanced Wing 14

Randomized and approximate algorithms that run at scale — sketching & streaming, similarity search, spectral methods, hashing, optimization & flows. Their soul is a probabilistic guarantee, shown empirically.

Sketching & Streaming 4

Morris Counter

Count to a billion in a byte — approximately. Store log log n bits and accept a random, but unbiased, estimate.

O(1)/update

Count–Min Sketch

Count every item in a stream using one small grid — never undercounting, and overcounting only a little.

O(d)/update

Reservoir Sampling

Pick k items uniformly at random from a stream of unknown length, in one pass and O(k) memory.

O(1)/item