06 — Advanced Sorting & Search¶
Phase 5 | Week 34 | Mar 23 – Mar 29, 2027
Every computer science curriculum teaches comparison-based sorting and proves O(n log n) is the lower bound. What gets skipped: that lower bound only applies to comparison-based algorithms. When you have additional information about your data — bounded integers, known range, uniform distribution — you can break the barrier. This file covers the cases where you can, and the practical search algorithms that matter for interviews.\n\n—
Why O(n log n) Is a Lower Bound for Comparison Sorting¶
A comparison-based sorting algorithm can be modeled as a decision tree. Each internal node is a comparison (is a[i] ≤ a[j]?). Each leaf is a permutation of the input.
For n elements, there are n! possible permutations. A binary tree with at least n! leaves has height ≥ log₂(n!).
By Stirling’s approximation: log₂(n!) ≈ n log₂(n) − n log₂(e) = Ω(n log n).
Conclusion: Any comparison-based sort needs Ω(n log n) comparisons in the worst case. This is tight — merge sort and heapsort achieve it.
The escape hatch: If you don’t use comparisons — if you exploit the structure of the data directly — you can do better. Counting sort, radix sort, and bucket sort all avoid the comparison lower bound by reading properties of individual elements directly.
Counting Sort: O(n + k)¶
When it applies: Elements are non-negative integers in a bounded range [0, k]. Works best when k = O(n) — i.e., the range is comparable to the array size.
Algorithm:
Create a count array
count[0..k]initialized to 0.For each element x in input:
count[x]++.Reconstruct sorted array: iterate count[0], count[1], …, outputting each value count[i] times.
def counting_sort(arr, k):
count = [0] * (k + 1)
for x in arr:
count[x] += 1
result = []
for v, c in enumerate(count):
result.extend([v] * c)
return result
Stable variant (needed as a subroutine for radix sort): Compute prefix sums of count, then place elements in output array from right to left.
Limitation: k can’t be too large (memory: O(k)). For elements with range [0, 10^9], counting sort uses 4 GB of memory — not feasible. Radix sort handles this.
Radix Sort: O(d · n)¶
When it applies: Non-negative integers. Sort by digits (or bits), one digit at a time, using stable counting sort as a subroutine.
LSD (Least Significant Digit) Radix Sort: Process digits from right (least significant) to left (most significant). After d passes, array is sorted.
def radix_sort(arr):
max_val = max(arr)
exp = 1 # 1, 10, 100, ...
while max_val // exp > 0:
counting_sort_by_digit(arr, exp)
exp *= 10
return arr
def counting_sort_by_digit(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for x in arr:
index = (x // exp) % 10
count[index] += 1
# prefix sums
for i in range(1, 10):
count[i] += count[i-1]
# build output (right to left for stability)
for i in range(n-1, -1, -1):
index = (arr[i] // exp) % 10
output[count[index] - 1] = arr[i]
count[index] -= 1
arr[:] = output
Complexity: d passes × O(n + b) each, where b is the base (10 for decimal, 256 for byte-level). For 32-bit integers with b=256: d=4 passes. Total: O(4 · (n + 256)) = O(n).
MSD (Most Significant Digit): Recursively sort by leading digit, then within each bucket sort by next digit. More flexible but harder to implement. Useful for strings (variable-length keys).
LSD vs. MSD: LSD is simpler and sufficient for fixed-width integers. MSD is needed for variable-length or lexicographic sorting.
Bucket Sort: O(n) Average¶
When it applies: Input values are uniformly distributed over a known range [a, b].
Algorithm:
Create n buckets, each covering a subrange of [a, b].
Distribute elements into buckets.
Sort each bucket individually (insertion sort within each bucket).
Concatenate.
Why O(n) average: With uniform distribution, each bucket has O(1) elements on average. Sorting each bucket takes O(1). Total: O(n).
Worst case: All elements in one bucket → O(n²) if using insertion sort. Not suitable when distribution is unknown or skewed.
Practical use: Floating-point data with known range, histogram-like problems, and as a conceptual predecessor to radix sort.
Quickselect: Kth Largest in O(n) Average¶
Problem: Find the kth largest (or smallest) element without sorting the entire array.
Naive approach: Sort in O(n log n), index at position k. Overkill.
Quickselect: Partition the array around a pivot (like quicksort’s partition step). If the pivot lands at position k, done. Otherwise, recurse on only the relevant half.
def quickselect(nums, k):
# Find kth largest = (n-k)th smallest
target = len(nums) - k
def partition(left, right):
pivot = nums[right]
store = left
for i in range(left, right):
if nums[i] <= pivot:
nums[i], nums[store] = nums[store], nums[i]
store += 1
nums[store], nums[right] = nums[right], nums[store]
return store
left, right = 0, len(nums) - 1
while left <= right:
pivot_idx = partition(left, right)
if pivot_idx == target:
return nums[pivot_idx]
elif pivot_idx < target:
left = pivot_idx + 1
else:
right = pivot_idx - 1
Average case: O(n). Pivot splits array roughly in half each time: T(n) = T(n/2) + O(n) → O(n).
Worst case: O(n²) with bad pivot selection (e.g., always choosing the max element). Mitigated by random pivot selection or median-of-3 pivot.
Better alternative for guaranteed O(n): Median-of-medians algorithm. Too complex for practical use; important for theoretical completeness.
Dutch National Flag Problem (3-Way Partition)¶
Problem: Given an array with 3 values (0, 1, 2), sort it in O(n) with O(1) space.
Algorithm (Dijkstra’s 3-way partition):
Maintain three regions: [0..low-1] = 0s, [low..mid-1] = 1s, [high+1..n-1] = 2s.
Invariant: mid..high is unexamined.
def sort_colors(nums):
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1; mid += 1
elif nums[mid] == 1:
mid += 1
else: # nums[mid] == 2
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
# don't increment mid — need to re-examine swapped element
O(n) time, O(1) space. Single pass.
Why it matters beyond the toy problem: This is the partition subroutine that makes quicksort handle duplicates efficiently (3-way quicksort). Arrays with many duplicates degenerate to O(n²) with 2-way partition; 3-way partition handles them in O(n) for the case where all elements are equal.
When to Use Which Sort¶
Scenario |
Sort |
Why |
|---|---|---|
General purpose, unknown data |
Merge sort / Timsort |
O(n log n) worst case, stable |
Integers in [0, 10^6] |
Counting sort |
O(n + k) if k is small |
Large integers, fixed width |
Radix sort |
O(d·n) |
Uniformly distributed floats |
Bucket sort |
O(n) average |
Find kth largest |
Quickselect |
O(n) average |
Sort with many duplicates |
3-way quicksort |
O(n) when all elements equal |
Partially sorted data |
Timsort |
Exploits existing runs |
External sort (doesn’t fit in RAM) |
External merge sort |
Minimizes I/O passes |
External Merge Sort (Intuition)¶
When data doesn’t fit in RAM (e.g., 100 GB file, 16 GB RAM):
Load chunks that fit in RAM, sort each, write sorted runs to disk.
Merge sorted runs using a k-way merge (min-heap of k elements, one per run).
Repeat until one sorted file remains.
Each pass reads and writes all data once: O(n/B) I/O operations per pass where B is block size. You need O(log(n/M)) passes where M is available memory.
This is how databases sort large tables and how distributed sorting (MapReduce-style) works at scale. Not an interview question in most contexts, but the correct answer when someone asks “how would you sort 100 GB?”
What Most Engineers Get Wrong¶
Using comparison sort when non-comparison sort is clearly better. If a problem gives you “elements in range [0, 100]” and asks to sort n = 10^6 elements, the answer is counting sort (O(n)), not merge sort (O(n log n)). The constraint in the problem statement is the signal. Read it.
Quickselect worst case. Stating “quickselect is O(n)” without qualification is wrong. It’s O(n) average case with random pivots. Worst case is O(n²). For guaranteed O(n), use median-of-medians (Floyd-Rivest algorithm). In practice, random pivot selection makes O(n²) astronomically unlikely.
Practice Problems¶
Medium¶
Sort Colors — LeetCode 75. Dutch national flag. O(n) single pass.
Kth Largest Element in an Array — LeetCode 215. Quickselect or min-heap. Both O(n) / O(n log k) worth knowing.
Hard¶
Maximum Gap — LeetCode 164. Bucket sort to find maximum gap in O(n). Requires the bucket size insight (pigeonhole principle).
Find Median from Data Stream — LeetCode 295. Two-heap approach. Not sorting per se, but order statistics in a stream.