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.
A jump-to index of every table row in this cheat sheet.
An interactive map of every table and concept in this topic.
Table 1: Sorting Algorithms
Sorting is the workhorse most interview questions and standard libraries lean on, so it pays to know which trade-off each method makes. The comparison-based sorts here — Quick, Merge, Tim, Heap — all live around the $O(n \log n)$ barrier but differ in stability, memory, and how they behave on real-world data, while the non-comparison sorts (Counting, Radix, Bucket) break that barrier entirely when your keys are small integers or uniformly spread. The simple quadratic sorts at the bottom aren't relics — insertion sort is fast enough on tiny or nearly sorted inputs that production hybrids like Tim Sort fall back to it.
| Algorithm | Example | Description |
|---|---|---|
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. | |
mid = (left + right) // 2mergesort(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. | |
minrun = compute_minrun(n)insertionSort for runs < minrunmerge 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. | |
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. | |
count = [0] * (max_val + 1)for x in arr: count[x] += 1for 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. | |
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. |