Sorting and search — the algorithmic building blocks of computer science, ordered by increasing sophistication
O(n²) worst
▷
Insertion Sort
Builds the sorted array one element at a time by inserting each into its correct position. Adaptive, stable, and optimal for small or nearly-sorted inputs.
Best O(n)
Avg O(n²)
Space O(1)
Stable
O(n²) always
○
Selection Sort
Repeatedly finds the minimum from the unsorted portion and swaps it into place. Simple, but always quadratic — no adaptivity.
Best O(n²)
Avg O(n²)
Space O(1)
Not Stable
O(n log n)
↔
Merge Sort
Divide-and-conquer: split in half, sort each recursively, merge the sorted halves. Guaranteed O(n log n) and stable — the gold standard when stability matters.
Best O(n log n)
Worst O(n log n)
Space O(n)
Stable
O(n log n) avg
⚡
Quick Sort
Pick a pivot, partition around it, recurse on each side. The fastest comparison sort in practice thanks to cache locality and small constants.
Best O(n log n)
Worst O(n²)
Space O(log n)
Not Stable
O(n log n)
△
Heap Sort
Build a max-heap, then repeatedly extract the maximum. Guaranteed O(n log n) and in-place — the worst-case optimal comparison sort for memory-constrained systems.
Best O(n log n)
Worst O(n log n)
Space O(1)
Not Stable
O(n + k)
№
Counting Sort
Counts occurrences of each value, then reconstructs the sorted output. Beats the O(n log n) comparison lower bound when the key range k is small.
Time O(n + k)
Space O(n + k)
Stable
O(d(n + k))
≡
Radix Sort
Sort digit by digit from least significant to most, using a stable sub-sort (counting sort) at each level. Linear time for fixed-width keys.
Time O(d(n+k))
Space O(n + k)
Stable
O(n)
→
Linear Search
Scan every element from start to end until the target is found or the array is exhausted. No preconditions — works on any collection.
Best O(1)
Avg O(n)
Worst O(n)
Unsorted OK
O(log n)
½
Binary Search
Halve the search space at each step by comparing the target to the middle element. The fundamental algorithm for sorted data and monotonic decision problems.
Best O(1)
Avg O(log n)
Worst O(log n)
Sorted Only
O(log log n) avg
∿
Interpolation Search
Estimates the target's position using value distribution rather than always probing the midpoint. Sub-logarithmic on uniformly distributed data.
Best O(1)
Avg O(log log n)
Worst O(n)
Uniform Data
O(log n)
×2
Exponential Search
Double the search range until the target is bracketed, then binary search within that range. Optimal when the target is near the beginning of an unbounded or very large sorted sequence.
Best O(1)
Worst O(log n)
Unbounded OK
Click any card to explore the full algorithm, motivation, and real-world application examples.