Algorithms & Data Structures

Five routines run over arrays that keep doubling. Watch how each one's step count answers the doubling: the same, one more, twice, a bit over twice, four times. That answer is its order.

Watch the real library implementation sweep the array again and again, swapping neighbors until a pass finds nothing left to swap.

Watch the real library implementation scan for the smallest remaining bar and swap it to the front, one final position per pass.

Watch the real library implementation execute line by line while it grows a sorted prefix through the array.

Watch the real library implementation insertion-sort the array at shrinking gaps, so far-apart bars move long distances in one hop.

Watch the real library implementation split the array down to single bars, then merge sorted halves back together through one auxiliary buffer.

Watch the real library implementation partition the array around pivots that land in their final slots and never move again.

Watch the real library implementation turn the array into a max heap, then retire the maximum to the end again and again.

Watch the real library implementation find natural runs, extend short ones with binary insertion, and merge them under the stack rules that keep it fast.

Watch the real library implementation sort three-digit values without a single comparison: bucket by ones, then tens, then hundreds.

Watch Batcher's odd-even merge network sort the array with a fixed schedule of compare-exchanges that never looks at the data to decide what happens next.

A sorted array answers a question with one read: the middle rules out half the cells. Watch the range halve to the target or close on nothing, and see why a scan needs n reads where this needs log n.

Variables, domains, and constraints between them: colour a map, place queens. Assign one variable at a time, prune what each choice rules out, and undo when a domain runs dry.

One array read as a tree that always knows its minimum: a push climbs, a pop sinks, and building from a batch costs less than pushing one by one, every hop bounded by the height.

A key's slot is computed from the key itself, so a lookup goes straight there. What happens when two keys want one slot, why the load factor governs every cost, and when the table doubles.

A forest of parent pointers answers 'are these two in the same set?' in a few hops: find climbs to a root, union hangs one root under another, and two tricks keep every tree nearly flat.

A search tree is only as fast as it is shallow. Watch sorted keys hang a plain tree into a chain, then watch an AVL tree rotate on the way back up and stay a few levels deep.

A sorted list with express lanes: coin flips at insertion set each key's tower, a lookup walks right and down in about 2 log n hops, and nothing ever rotates.

Two arrays make a set over small integers with O(1) insert, remove, membership, and clear, no clearing of memory needed: dense packs the members, sparse points each value at its slot.

A row of bits and a few hashes answer 'have I seen this?' with no false negatives and a tunable chance of a false positive, in space far smaller than the keys themselves.

A few rows of counters, each indexed by its own hash, estimate how often anything appeared in a stream: never below the truth, rarely far above it, in space that ignores the stream's length.

Count distinct items in a stream with a few bytes: hash each one, let the longest run of leading zeros in each bucket estimate the count, and average the buckets harmonically.

Insert into a tree without touching the old one: copy the path from the root, share every other subtree, and every version stays readable forever at a logarithmic cost per change.

Visit every reachable node once with one loop and a frontier. Take from the front and it ripples out in layers; take from the back, marking nodes as they come off, and it plunges down a branch.

Settle the nearest node, relax its edges, repeat. A heap keeps the nearest at hand, a stale entry is skipped, and every settled distance is final because no edge is negative. BFS, ordered by distance.

Dijkstra with a compass: rank the open set by the cost so far plus an estimate of the cost to go. An estimate that never overstates keeps the path optimal in fewer expansions; overstate it, it errs.

Order the nodes of a directed graph so every edge points forward: peel off nodes with nothing left pointing at them, or finish a depth-first walk and read it backwards.

Connect every waypoint with the least total length: Kruskal takes edges cheapest first and skips any that close a cycle; Prim grows one tree from a start by its cheapest frontier edge.

Push as much as the pipes allow from source to sink: find a path with room, send its bottleneck, record how to undo it, repeat; the final blocked set is the minimum cut.

A page is important if important pages link to it: rank flows along links each round, a damping share teleports anywhere, and the ranks settle to a fixed point no matter where they start.

Where a symbol repeats, send it once with a count. The simplest compressor there is: two bytes per run, a scanline of a bitmap shrinks, a line of prose doubles, and a cap splits the long runs.

Count the symbols, heap them, merge the two lightest until one root remains. The paths down the tree are the code words: short for common symbols, long for rare ones, never one a prefix of another.

Text repeats itself. At each position, look back through a window for the longest copy of what comes next and send a pointer instead of the characters. The decoder just copies. The other half of zip.

Give each symbol a slice of the unit interval, keep each symbol's slice of what is left, and send the shortest fraction inside: the message costs its information plus two bits, never a bit a symbol.

The fewest coins for an amount, defined by its own smaller copies. Plain recursion solves the same amounts again and again; a memo solves each once, and a table needs no recursion at all.