Algorithms Cheat Sheet

Updated 2026-04-29

Next Topic: Approximation Algorithms and Heuristics Cheat Sheet

Algorithms are step-by-step computational procedures for solving problems — ranging from simple tasks like searching and sorting to complex optimization and graph traversal challenges. They form the foundation of computer science, enabling efficient data processing across fields like artificial intelligence, databases, networking, and systems design. Understanding algorithmic paradigms — such as divide-and-conquer, dynamic programming, greedy methods, and backtracking — equips you to select the right strategy for a problem's constraints. A key insight: the best algorithm isn't always the fastest in theory; cache locality, constant factors, and input characteristics often matter more in practice than asymptotic complexity alone.

What This Cheat Sheet Covers

This topic spans 21 focused tables and 166 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.

Table 1: Sorting AlgorithmsTable 2: Searching AlgorithmsTable 3: Dynamic ProgrammingTable 4: Greedy AlgorithmsTable 5: Divide and ConquerTable 6: BacktrackingTable 7: Graph Algorithms — Shortest PathTable 8: Graph Algorithms — Minimum Spanning TreeTable 9: Graph Algorithms — Traversal and TopologyTable 10: Graph Algorithms — Cycle DetectionTable 11: Network Flow AlgorithmsTable 12: String AlgorithmsTable 13: Tree AlgorithmsTable 14: Advanced Data StructuresTable 15: Algorithmic Paradigms and TechniquesTable 16: Computational GeometryTable 17: Complexity ClassesTable 18: Recursion PatternsTable 19: Hashing TechniquesTable 20: Approximation and Randomized AlgorithmsTable 21: Number Theory Algorithms

Table 1: Sorting Algorithms

Algorithm	Example	Description
Quick Sort	`pivot = arr[high]` `partition(arr, low, high)` `quicksort(arr, low, pi-1)`	• Divide-and-conquer sort that picks a pivot, partitions around it, and recursively sorts • average $O(n \log n)$ , worst $O(n^2)$ but cache-friendly and widely used in practice.
Merge Sort	`mid = (left + right) // 2` `mergesort(arr, left, mid)` `merge(arr, left, mid, right)`	• Stable divide-and-conquer sort that always runs in $O(n \log n)$ time • requires $O(n)$ extra space but guarantees consistent performance.
Tim Sort	`minrun = compute_minrun(n)` `insertionSort for runs < minrun` `merge adjacent runs`	• Hybrid of merge sort and insertion sort • $O(n \log n)$ worst case, optimized for real-world data, used in Python and Java standard libraries.
Heap Sort	`buildMaxHeap(arr)` `swap(arr[0], arr[i])` `heapify(arr, 0, i)`	• In-place sort using a binary heap • $O(n \log n)$ time, $O(1)$ space, but not stable and slower in practice than Quick Sort due to poor cache behavior.
Counting Sort	`count = [0] * (max_val + 1)` `for x in arr: count[x] += 1` `for i, c in enumerate(count): output.extend([i] * c)`	• Non-comparison integer sort that counts occurrences • $O(n + k)$ time where $k$ is range, efficient when $k = O(n)$ but requires extra space.
Radix Sort	`for digit in range(num_digits):` `countingSortByDigit(arr, digit)`	• Non-comparison sort that processes digits from least to most significant • $O(d(n + k))$ where $d$ is digits, works well for integers with bounded digit count.

Table 1: Sorting Algorithms

Algorithm	Example	Description
Quick Sort	`pivot = arr[high]` `partition(arr, low, high)` `quicksort(arr, low, pi-1)`	• Divide-and-conquer sort that picks a pivot, partitions around it, and recursively sorts • average $O(n \log n)$ , worst $O(n^2)$ but cache-friendly and widely used in practice.
Merge Sort	`mid = (left + right) // 2` `mergesort(arr, left, mid)` `merge(arr, left, mid, right)`	• Stable divide-and-conquer sort that always runs in $O(n \log n)$ time • requires $O(n)$ extra space but guarantees consistent performance.
Tim Sort	`minrun = compute_minrun(n)` `insertionSort for runs < minrun` `merge adjacent runs`	• Hybrid of merge sort and insertion sort • $O(n \log n)$ worst case, optimized for real-world data, used in Python and Java standard libraries.
Heap Sort	`buildMaxHeap(arr)` `swap(arr[0], arr[i])` `heapify(arr, 0, i)`	• In-place sort using a binary heap • $O(n \log n)$ time, $O(1)$ space, but not stable and slower in practice than Quick Sort due to poor cache behavior.
Counting Sort	`count = [0] * (max_val + 1)` `for x in arr: count[x] += 1` `for i, c in enumerate(count): output.extend([i] * c)`	• Non-comparison integer sort that counts occurrences • $O(n + k)$ time where $k$ is range, efficient when $k = O(n)$ but requires extra space.
Radix Sort	`for digit in range(num_digits):` `countingSortByDigit(arr, digit)`	• Non-comparison sort that processes digits from least to most significant • $O(d(n + k))$ where $d$ is digits, works well for integers with bounded digit count.