Algorithm Reference

Repeatedly steps through the list, compares adjacent elements and swaps them if out of order. Each pass bubbles the largest unsorted element to its final position. Simple to understand but inefficient for large datasets.

Finds the minimum element in the unsorted portion and places it at the sorted region's end. Performs at most n-1 swaps, making it useful when write operations are expensive. Does not benefit from partially sorted input.

An enhancement of selection sort that simultaneously finds both the minimum and maximum values in each pass, placing them at both ends of the unsorted region. Halves the number of passes while maintaining the same O(n²) comparisons.

Builds a sorted subarray one element at a time by taking each new element and inserting it into the correct position in the already-sorted left portion. Efficient for small datasets and nearly-sorted data, with O(n) best-case performance.

A bidirectional variant of bubble sort that alternates passes left-to-right and right-to-left. Moves small elements to the front faster than standard bubble sort and handles certain nearly-sorted cases more efficiently.

Moves along the list like a garden gnome — if the current pair is in order it steps forward, otherwise it swaps and steps back. Equivalent to insertion sort but implemented as a single traversal pointer bouncing back and forth.

Alternates between comparing odd-indexed and even-indexed adjacent pairs across the entire array simultaneously. Originally designed for parallel processors, it is equivalent to bubble sort when run sequentially but maps naturally to SIMD hardware.

Minimizes the total number of writes by decomposing the permutation into cycles. Each element is moved directly to its final position with exactly one write per displacement. Optimal for write-expensive storage like flash memory.

Sorts by performing "flips" — reversing a prefix of the array. Finds the maximum in the unsorted region, flips it to the top, then flips it to its final position. Named after the culinary process of stacking pancakes by size.

Improves on bubble sort by comparing elements separated by a large gap that shrinks by a factor of 1.3 each pass. Eliminates "turtles" (small values near the end) far faster than bubble sort and approaches O(n log n) in practice.

Repeatedly extracts naturally increasing subsequences ("strands") from the input and merges them into the output list. Performance degrades on random data but is very fast when many ascending runs already exist in the data.

A variant of selection sort that groups all elements equal to the current minimum value and places them all at once. Useful when many duplicate keys exist, reducing passes for inputs with low cardinality.

Similar to bubble sort but compares each element with all subsequent elements and swaps immediately on finding a smaller value, rather than bubbling. Produces fewer total swaps than bubble sort on average while maintaining O(n²) comparisons.

Divides the array in half recursively until single elements remain, then merges sorted halves back together. Guarantees O(n log n) in all cases with stable ordering. Requires O(n) auxiliary space, making it the standard choice for linked lists.

Splits the array into three parts instead of two, reducing the recursion depth to log₃(n). The three-way merge step is slightly more complex but reduces passes by roughly 37%, benefiting external sorting scenarios where I/O is costly.

Selects a pivot element and partitions the array so all smaller elements precede it and all larger follow, then recurses on each partition. Achieves excellent cache performance in practice and is the most-used general-purpose sort in standard libraries.

Uses two pivots to partition the array into three regions: less than left pivot, between pivots, and greater than right pivot. Java's Arrays.sort() uses this variant; empirically requires about 5% fewer comparisons than single-pivot quicksort.

Begins with quicksort and switches to heapsort when recursion depth exceeds 2·log(n), guaranteeing O(n log n) worst case. Falls back to insertion sort for small partitions. Used in C++ std::sort — combines the best of all three algorithms.

Builds a max-heap from the array, then repeatedly extracts the maximum element and places it at the end, shrinking the heap each time. Achieves O(n log n) worst case with O(1) space, but poor cache locality makes it slower than quicksort in practice.

Generalizes insertion sort by comparing elements separated by a decreasing gap sequence. Early passes with large gaps move elements far quickly; final pass (gap=1) is a standard insertion sort on a nearly-sorted array. Gap sequence choice strongly affects performance.

Python's and Java's default sort: identifies natural runs in the data (ascending or descending sequences), sorts small runs with insertion sort, then merges them using a stack-based strategy. Extremely fast on real-world data that contains pre-sorted segments.

Constructs bitonic sequences (first increasing then decreasing) and merges them using a sorting network. All comparisons are data-independent, making it ideal for parallel hardware like GPUs. Not practical for sequential CPU-based sorting.

Recursively compares elements at opposite ends of a range and swaps if needed, then splits the range in two and recurses on each half. After each full pass the array gets closer to sorted. Achieves O(n log n) average with an elegant recursive structure.

A heap sort variant by Dijkstra that uses a Leonardo heap — a sequence of heaps whose sizes are Leonardo numbers. Achieves O(n) on sorted input while maintaining O(n log n) worst case. Theoretically interesting but complex to implement correctly.

Deals cards into piles following patience-game rules (each card goes on the leftmost pile whose top is greater), then merges piles using a priority queue. The number of piles equals the length of the longest increasing subsequence — useful for that computation.

Builds a complete binary tree tournament where each node holds the winner of its subtree. The global winner is extracted, replaced with a sentinel, and the tournament is replayed efficiently. Forms the conceptual basis for heapsort and priority queues.

Inserts all elements into a binary search tree, then performs an in-order traversal to retrieve them in sorted order. O(n log n) average with a self-balancing BST. The building step dominates; O(n²) worst case with an unbalanced tree on sorted input.

An in-place stable merge sort that divides the array into blocks, uses internal buffers to facilitate merges without extra memory. Achieves O(n log n) time and O(1) space with stable ordering — the only known algorithm with all three properties simultaneously.

Pattern-Defeating Quicksort detects adversarial patterns (all equal, reverse-sorted, organ-pipe) and rearranges the input to defeat them before partitioning. Used in Rust's sort_unstable and several modern C++ implementations for its near-optimal practical performance.

Insertion sort with gaps — inserts elements into a spaced array (leaving slack between elements) so binary search finds the insertion point and fewer elements need shifting. Achieves O(n log n) average while maintaining the simplicity of insertion sort's logic.

Identifies the longest increasing run in the data, then "drops" the remaining out-of-order elements into a side list, sorts that list, and merges back. Extremely fast when fewer than ~10% of elements are out of order — approaches O(n) on nearly-sorted data.

Builds a Cartesian tree (a BST satisfying the heap property) from the input in O(n) time, then extracts the minimum repeatedly via heap operations. Achieves O(n log n) overall; the tree construction step adapts to presortedness, being O(n) for sorted input.

Uses a "weak heap" — a relaxed heap variant where each node is greater than all nodes in its right subtree. Requires n−1 comparisons for merge, reducing the total comparisons to roughly 1.5n log n, fewer than standard heapsort in practice.

The merge-insertion sort by Ford and Johnson (1959) uses an optimal sequence of binary insertions to minimize comparisons, approaching the information-theoretic lower bound. Primarily of theoretical interest — the comparison count is optimal but performance on real hardware is poor.

A parallel sorting network by Ken Batcher that separates elements by odd/even indices and recursively merges them. Has the same O(n log² n) depth as bitonic sort but half the number of comparators, making it more hardware-efficient for parallel implementation.

Counts occurrences of each distinct value and computes cumulative counts to directly calculate each element's output position. Linear O(n+k) time when the value range k is not much larger than n. No comparisons are made — elements jump directly to final positions.

Sorts integer keys digit by digit starting from the least significant digit, using a stable sort (typically counting sort) for each digit pass. Requires d passes where d is the number of digits. Faster than comparison sorts for integers with bounded key size.

Processes digits from most significant to least, recursively sorting each bucket. Can terminate early when a bucket has one element. More flexible than LSD — handles variable-length strings naturally and can be implemented as an in-place variant, unlike LSD radix.

Distributes elements into a fixed number of buckets covering a value range, sorts each bucket individually (often with insertion sort), then concatenates. O(n) average when input is uniformly distributed. Degrades to O(n²) when all elements fall into one bucket.

Also called Bead Sort — simulates beads sliding down poles: arrange values as rows of beads on vertical poles and let them fall under gravity. Each row collects into a sorted value. A physical analog computation that is O(1) in hardware but O(n·max) when simulated in software.

Creates one "hole" (bucket) per possible value, deposits each element into its hole, then reads them back in order. Similar to counting sort but stores actual elements rather than counts. Ideal when n ≈ k — the number of elements closely matches the value range.

A distribution sort that classifies elements into m linear buckets based on a uniform distribution assumption, permutes them in-place into their approximate position, then finishes with insertion sort. Achieves O(n) for uniformly distributed data with very low constant factors.

Recursively sorts the first 2/3, last 2/3, then first 2/3 of the array again. Provably correct but has O(n^2.71) complexity — worse than any practical algorithm. Named for the Three Stooges' chaotic and inefficient approach to problem-solving.

Spawns one thread per element that sleeps for a duration proportional to its value. Threads wake up in value order and each appends its element to the output. Correct in theory but relies on OS scheduling accuracy — not deterministic and not actually O(1).

A multiply-recursive algorithm explicitly designed to be as slow as possible while still being correct. Recursively sorts the first half, the second half, then reduces the maximum to the end and recurses on all but the last element. Complexity is worse than any polynomial.

A satirical "sort" that achieves O(n) time by simply removing any element that is out of order. The result is a sorted array — but it may be missing elements. Guaranteed to produce a sorted subsequence of the original data.

Randomly shuffles the array and checks if it is sorted. If not, shuffles again. Expected O((n+1)!) time — approximately 40,000 years for 12 elements. A standard joke algorithm used to illustrate what not to do when designing a sorting algorithm.

Explores all neighbors at each depth before moving deeper, guaranteeing the shortest path on unweighted graphs. Uses a queue to maintain the frontier. Visits every reachable node, making it thorough but memory-intensive for large graphs.

Explores as deep as possible along each branch before backtracking, using a stack (or recursion). Uses O(depth) memory versus BFS's O(width), making it practical for very deep graphs. Does not guarantee the shortest path on unweighted graphs.

Iterative-Deepening DFS performs repeated depth-limited DFS with an increasing depth cutoff. Combines BFS's completeness and optimality guarantee with DFS's O(d) memory footprint. The key insight: repeated work is dominated by the final iteration.

Runs two simultaneous BFS frontiers — one from start, one from goal — stopping when they meet. Explores only O(b^(d/2)) nodes instead of O(b^d), a massive speedup for large graphs. The meeting point detection is the critical implementation challenge.

A wall-following maze algorithm that keeps the left hand on the wall at all times. Guaranteed to reach the exit in any simply-connected maze (one with no isolated walls). Fails on mazes with disconnected wall segments — the agent may loop forever.

The mirror of Trace Left — keeps the right hand on the wall instead. Explores a different set of passages and may find the goal faster or slower depending on the maze topology. Both hand-following algorithms trace perimeter paths rather than exploring efficiently.

Finds shortest paths from a source node to all reachable nodes in a weighted graph with non-negative edge weights. Uses a priority queue to always process the closest unvisited node first. The foundation of GPS routing and most practical shortest-path applications.

Extends Dijkstra with a heuristic function h(n) estimating cost to goal, prioritizing nodes with lowest f(n) = g(n) + h(n). With an admissible heuristic, A* is guaranteed optimal and visits far fewer nodes than Dijkstra. The standard algorithm for game AI and navigation.

Runs A* simultaneously from both start and goal, using heuristics to focus each frontier toward the other. The frontiers meet in the middle. Correct termination requires careful handling — naive implementations can miss the optimal path when frontiers collide.

Two Dijkstra searches expanding simultaneously from start and goal, stopping when any node is settled by both frontiers. Used in real road-network routing systems; combined with contraction hierarchies, it powers Google Maps and similar services.

Iterative-Deepening A* applies A*'s f-cost threshold iteratively instead of maintaining a priority queue. Uses O(d) memory — the only optimal heuristic search algorithm with linear space complexity. The standard solver for sliding puzzles and many combinatorial problems.

Caches the fringe of IDA* — a two-list structure (now/later) instead of IDA*'s repeated full re-expansion. Achieves A*-equivalent optimality with much lower overhead than A* in practice: no priority queue, O(V) memory, and faster per-iteration constant factors.

A best-first search that restricts the frontier to the W best candidates at each depth level, discarding all others. Trades completeness and optimality for dramatically reduced memory. Used extensively in machine translation, speech recognition, and NLP decoding.

An any-angle path planning algorithm that allows path segments to pass through grid corners rather than being constrained to grid edges. Uses line-of-sight checks to skip intermediate waypoints and produces smoother, shorter paths than A* on grid maps.

Recursive Best-First Search simulates A* using only O(bd) memory by tracking the best alternative f-value in each branch. When a subtree's cost exceeds the sibling's best-known cost, it is abandoned and re-explored later. Optimal and complete with heuristic-guided efficiency.

A weighted blend of Dijkstra's distance-from-source and A*'s heuristic distance-to-goal. Adjusting the blend weight shifts behavior from Dijkstra (full coverage) to A* (directed). Useful for visualizing how the balance between exploration and goal-direction affects search shape.

Accelerates A* on uniform-cost grids by "jumping" over symmetrically equivalent paths, only adding nodes to the open set when forced neighbors exist. Can be 10–100× faster than A* on open grid maps. Restricted to uniform-cost, obstacle-based grid graphs.

Relaxes all edges V-1 times, handling negative edge weights that Dijkstra cannot process. Detects negative cycles on the V-th iteration. O(VE) is much slower than Dijkstra but required for graphs with negative weights, such as financial arbitrage models.

Shortest Path Faster Algorithm is a queue-based Bellman-Ford optimisation that only re-relaxes a node when its distance improves. O(E) average on random graphs. Used in competitive programming for negative-weight graphs when Bellman-Ford is too slow.

Always moves to the neighbor that minimizes heuristic distance to goal. Greedy, fast, and uses O(1) memory, but easily trapped at local minima or plateaus. Not complete — may fail to reach the goal even when a path exists.

Chooses randomly among improving neighbors rather than always picking the best. The randomness helps escape some ridges and plateaus that trap deterministic hill climbing. Still not complete, but explores more of the state space before getting stuck.

Accepts worse moves with probability e^(-delta/T) where temperature T decreases over time. Early high-temperature phases explore widely; late low-temperature phases focus exploitation. Modeled on metallurgical annealing — cooling slowly produces better crystal structure.

A probabilistic search that blends random exploration with heuristic guidance. At each step there is some probability of choosing randomly versus greedily. Balances exploration and exploitation without a formal temperature schedule like simulated annealing.

Moves to a uniformly random neighbor at each step with no memory of past positions. Guaranteed to eventually reach any connected node (recurrent on 2D grids) but expected hitting time scales as O(n²) for an n-node grid — practically useless for navigation.

A random walk where moves toward the goal are chosen with higher probability than moves away. Reaches the goal faster than a uniform random walk while still exploring non-greedily. Models biological chemotaxis — bacteria move toward nutrients with probabilistic gradient-following.

Uses only h(n) — the heuristic estimate to goal — to order the priority queue, ignoring the cost already paid to reach n. Finds goals quickly on open terrain but is not optimal and can be led astray by misleading heuristics. Essentially A* with g(n) removed.

Teleports to a random cell each step and checks if it is the goal. Guaranteed to terminate in finite expected time on a finite grid, but expected steps scale as O(n²) for an n-cell grid. Exists purely to illustrate how not to search.

Attempts to visit every cell before reaching the goal — intentionally maximizing the path length. Moves to whichever unvisited neighbor is farthest from the goal. A humorous counterpoint to A*, illustrating how anti-heuristics produce comically bad routes.