Algorithms & Data Structures
An algorithm is a finite, unambiguous sequence of well-defined instructions for solving a class of problems. A data structure is an organization of data that enables efficient access and modification. Together they form the mechanical foundation of all computation. This skill catalogs the canonical algorithms and data structures with complexity analysis, implementation notes, and selection heuristics.
Agent affinity: knuth (algorithm analysis, literate implementation), turing (computability, theoretical limits)
Concept IDs: code-sorting-algorithms, code-searching-algorithms, code-big-o-notation, code-dynamic-programming
Complexity Analysis at a Glance
Before studying individual algorithms, internalize the complexity hierarchy. Every algorithm has a time cost and a space cost, each expressed as a function of input size n.
| Class | Name | Example |
|---|---|---|
| O(1) | Constant | Array index access, hash table lookup (average) |
| O(log n) | Logarithmic | Binary search, balanced BST lookup |
| O(n) | Linear | Linear search, single traversal |
| O(n log n) | Linearithmic | Merge sort, heap sort, efficient comparison sorts |
| O(n^2) | Quadratic | Bubble sort, insertion sort (worst), naive string matching |
| O(n^3) | Cubic | Naive matrix multiplication, Floyd-Warshall |
| O(2^n) | Exponential | Brute-force subset enumeration, naive recursive Fibonacci |
| O(n!) | Factorial | Brute-force permutation, naive TSP |
Big-O gives the asymptotic upper bound. Big-Omega gives the lower bound. Big-Theta gives the tight bound (both upper and lower). When we say "merge sort is O(n log n)," we mean its worst-case running time grows no faster than c * n * log(n) for some constant c and sufficiently large n. More precisely, merge sort is Theta(n log n) because its best, average, and worst cases all share this growth rate.
Amortized analysis applies when individual operations vary in cost but the average over a sequence is predictable. The classic example is dynamic array resizing: a single push may cost O(n) when the array doubles, but amortized over n pushes, each costs O(1).
Part 1 -- Sorting Algorithms
Sorting is the most studied problem in computer science. Comparison-based sorting has a proven lower bound of Omega(n log n) -- no comparison sort can do better in the worst case. Non-comparison sorts (radix, counting, bucket) can beat this bound when the data admits it.
1.1 -- Bubble Sort
Mechanism: Repeatedly walk the array, swapping adjacent elements that are out of order. After pass k, the k-th largest element is in its final position.
Complexity: O(n^2) time worst/average, O(n) best (already sorted, with early-exit optimization). O(1) space. Stable.
When to use: Almost never in production. Its value is pedagogical -- it is the simplest sorting algorithm to understand and proves that sorting is achievable through local comparisons alone.
The early-exit optimization. If a full pass completes with zero swaps, the array is sorted. This gives O(n) best case, making bubble sort adaptive -- it benefits from pre-existing order.
1.2 -- Insertion Sort
Mechanism: Build the sorted portion one element at a time. For each new element, shift larger elements right and insert into the correct position.
Complexity: O(n^2) worst/average, O(n) best (nearly sorted). O(1) space. Stable. Adaptive.
When to use: Small arrays (n < 20-50), nearly sorted data, online sorting (elements arrive one at a time). Many optimized sort implementations (including Timsort) use insertion sort for small partitions.
Why it beats bubble sort. Insertion sort performs at most n-1 comparisons on sorted input and does fewer swaps on average because it moves elements directly to their correct position rather than bubbling them one step at a time.
1.3 -- Selection Sort
Mechanism: Find the minimum element in the unsorted portion and swap it to the front. Repeat.
Complexity: O(n^2) in all cases. O(1) space. Not stable (swaps can break equal-element ordering). Not adaptive.
When to use: When write operations are expensive (flash memory, EEPROM) -- selection sort performs exactly n-1 swaps regardless of input. This is its only practical advantage.
1.4 -- Merge Sort
Mechanism: Divide the array in half, recursively sort each half, merge the sorted halves.
Complexity: Theta(n log n) in all cases. O(n) auxiliary space (for the merge buffer). Stable.
The merge operation. Two pointers walk the two sorted halves. At each step, the smaller element is copied to the output. This is O(n) per level, and there are log(n) levels, giving n log n total.
When to use: When stability is required, when worst-case guarantees matter, when data is on disk (merge sort's sequential access pattern is cache-friendly for external sorting). Java's Arrays.sort for objects uses a merge sort variant (Timsort).
Recurrence relation: T(n) = 2T(n/2) + O(n). By the Master Theorem (case 2), T(n) = Theta(n log n).
1.5 -- Quick Sort
Mechanism: Choose a pivot, partition the array so all elements less than the pivot come before it and all greater come after, recursively sort the partitions.
Complexity: O(n log n) average, O(n^2) worst (pathological pivot choices). O(log n) space (recursion stack, in-place). Not stable (Lomuto/Hoare partition swaps non-adjacent elements).
Pivot selection strategies. Random pivot gives O(n log n) expected time. Median-of-three (first, middle, last) avoids worst case on sorted input. Introselect (switch to heap sort after recursion depth exceeds 2 log n) guarantees O(n log n) worst case -- this is introsort, used by C++ std::sort.
When to use: Default choice for in-memory sorting when stability is not required. Cache performance is excellent (sequential access within partitions). In practice, quicksort with good pivot selection beats merge sort due to lower constant factors.
Why O(n^2) worst case is rare. With random pivot selection, the probability of O(n^2) behavior is vanishingly small. The expected number of comparisons is 2n ln n, approximately 1.39 n log2 n.
1.6 -- Heap Sort
Mechanism: Build a max-heap from the array (O(n) via Floyd's algorithm), then repeatedly extract the maximum and place it at the end.
Complexity: Theta(n log n) in all cases. O(1) space. Not stable.
When to use: When guaranteed O(n log n) is needed without the O(n) auxiliary space of merge sort. The constant factor is larger than quicksort's, making it slower in practice for in-memory sorting. Used as the fallback in introsort.
1.7 -- Radix Sort (Non-Comparison)
Mechanism: Sort by each digit position, from least significant to most significant, using a stable sub-sort (counting sort) at each position.
Complexity: O(d * (n + k)) where d is the number of digits and k is the base. For fixed-width integers, this is O(n). Space: O(n + k).
When to use: When sorting integers or fixed-length strings where the number of digits d is small relative to log n. Radix sort is not comparison-based and therefore not subject to the Omega(n log n) lower bound.
Sorting Selection Heuristic
| Situation | Algorithm | Reason |
|---|---|---|
| Small array (n < 50) | Insertion sort | Low overhead, adaptive |
| General purpose, stability needed | Merge sort / Timsort | Guaranteed O(n log n), stable |
| General purpose, in-place | Quicksort (introsort) | Best average-case cache behavior |
| Guaranteed worst-case, in-place | Heap sort | No auxiliary space, no pathological cases |
| Integers, fixed-width keys | Radix sort | O(n) when d is bounded |
| Nearly sorted | Insertion sort / Timsort | Adaptive algorithms exploit existing order |
| Minimizing writes | Selection sort | Exactly n-1 swaps |
Part 2 -- Searching Algorithms
2.1 -- Linear Search
Mechanism: Walk the collection from start to end, checking each element.