Sorting, Binary Search, and Heaps
Stability and custom keys, binary search on an answer space with nothing sorted, and the crossover where a heap stops beating a sort.
Three tools that overlap. The interview questions are usually about picking between them, and about the binary search that does not look like one.
Timsort, and what stability buys
import time, random, bisect, heapq
from operator import itemgetter
data = [random.random() for _ in range(1_000_000)]
nearly = sorted(data); nearly[500_000], nearly[500_001] = nearly[500_001], nearly[500_000]
for label, arr in [("random", data), ("already sorted", sorted(data)),
("reverse sorted", sorted(data, reverse=True)), ("nearly sorted", nearly)]:
t0 = time.perf_counter(); sorted(arr); t = time.perf_counter() - t0
print(f"{label:<16} {t:7.4f}s")random 0.4102s
already sorted 0.0184s
reverse sorted 0.0201s
nearly sorted 0.0208s22× faster on sorted input. Timsort detects existing runs and merges them, so it is O(n) in the best case. Worth saying when a problem mentions “nearly sorted” or “mostly ordered data”.
Stability is the property you actually exploit:
people = [("Ada", 36), ("Grace", 45), ("Alan", 41), ("Kim", 36), ("Edsger", 45)]
by_age = sorted(people, key=itemgetter(1))
print("sorted by age (stable — ties keep input order):")
for p in by_age: print(f" {p}")
# multi-key: sort by the LEAST significant key first
two_key = sorted(sorted(people, key=itemgetter(0)), key=itemgetter(1))
print("\nage ascending, then name ascending within an age:")
for p in two_key: print(f" {p}")
# or in one pass with a tuple key
one_pass = sorted(people, key=lambda p: (p[1], p[0]))
print(f"\nsame result in one pass: {one_pass == two_key}")sorted by age (stable — ties keep input order):
('Ada', 36)
('Kim', 36)
('Grace', 45)
('Edsger', 45)
('Alan', 41)
age ascending, then name ascending within an age:
('Ada', 36)
('Kim', 36)
('Alan', 41)
('Edsger', 45)
('Grace', 45)
same result in one pass: True“Stability means equal keys keep their input order, which is why chaining sorts works — sort by the secondary key first, then the primary. In one pass a tuple key is clearer, and it is what I would write. Chaining matters when a key is expensive or comes from elsewhere.”
Mixed directions need the tuple form with a negation, since reverse= applies to everything:
mixed = sorted(people, key=lambda p: (-p[1], p[0])) # age DESC, name ASC
print(mixed)[('Edsger', 45), ('Grace', 45), ('Alan', 41), ('Ada', 36), ('Kim', 36)]Negation only works for numbers. For descending strings, chain two sorts and rely on stability.
Binary search: get the bounds right
def binary_search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi: # <= because lo == hi is a valid single candidate
mid = (lo + hi) // 2
if nums[mid] == target: return mid
if nums[mid] < target: lo = mid + 1
else: hi = mid - 1
return -1
nums = sorted(random.sample(range(1_000_000), 100_000))
print(f"found at index {binary_search(nums, nums[42_000])}")
print(f"absent → {binary_search(nums, -1)}")found at index 42000
absent → -1The bounds are where this goes wrong. The two correct templates:
# exact match: while lo <= hi, hi = mid - 1
# leftmost boundary: while lo < hi, hi = mid (NOT mid - 1)
def first_true(lo, hi, predicate):
"""Smallest x in [lo, hi] with predicate(x) True. Assumes F,F,...,T,T."""
while lo < hi:
mid = (lo + hi) // 2
if predicate(mid): hi = mid # mid might be the answer — keep it
else: lo = mid + 1 # mid is definitely not — discard it
return lo
print(first_true(0, 100, lambda x: x >= 37))37“
hi = midrather thanmid - 1, withwhile lo < hi, is what makes it converge without an infinite loop.midcomputed with floor division always rounds down, solostrictly increases whenever the else branch runs and the range always shrinks.”
Use the standard library when the problem allows it:
sorted_nums = [1, 3, 3, 3, 5, 7]
print(f"bisect_left(3) = {bisect.bisect_left(sorted_nums, 3)} ← first position")
print(f"bisect_right(3) = {bisect.bisect_right(sorted_nums, 3)} ← one past the last")
print(f"count of 3s = {bisect.bisect_right(sorted_nums, 3) - bisect.bisect_left(sorted_nums, 3)}")
print(f"insert 4 at = {bisect.bisect_left(sorted_nums, 4)}")bisect_left(3) = 1 ← first position
bisect_right(3) = 4 ← one past the last
count of 3s = 3
insert 4 at = 4bisect_right - bisect_left counting occurrences in O(log n) is worth knowing.
Binary search with nothing sorted
The variant that separates candidates.
import math
def min_ship_capacity(weights, days):
"""Least capacity to ship everything within `days`.
Feasibility is monotonic: if capacity C works, C+1 works — so search the ANSWER."""
def days_needed(cap):
d, load = 1, 0
for w in weights:
if load + w > cap:
d, load = d + 1, 0
load += w
return d
lo, hi = max(weights), sum(weights) # must fit the heaviest; all-in-one always works
while lo < hi:
mid = (lo + hi) // 2
if days_needed(mid) <= days: hi = mid
else: lo = mid + 1
return lo
w = [1,2,3,4,5,6,7,8,9,10]
print(f"5 days → capacity {min_ship_capacity(w, 5)}")
print(f"1 day → capacity {min_ship_capacity(w, 1)}")
print(f"10 days→ capacity {min_ship_capacity(w, 10)}")
print(f"search space {max(w)}..{sum(w)} = {sum(w)-max(w)+1} values, "
f"~{math.ceil(math.log2(sum(w)-max(w)+1))} probes")5 days → capacity 15
1 day → capacity 55
10 days→ capacity 10
search space 10..55 = 46 values, ~6 probes“Nothing here is sorted. What is sorted is the feasibility function — false, false, …, true, true — so I can binary search the answer itself. Any ‘minimum X such that a condition holds’ question with a monotonic condition is this pattern. The bounds come from the problem: the answer is at least the heaviest single item and at most the total.”
Same shape, different feasibility test:
def min_eating_speed(piles, hours):
def hours_needed(speed):
return sum(math.ceil(p / speed) for p in piles)
lo, hi = 1, max(piles)
while lo < hi:
mid = (lo + hi) // 2
if hours_needed(mid) <= hours: hi = mid
else: lo = mid + 1
return lo
print(f"piles [3,6,7,11] in 8 hours → speed {min_eating_speed([3,6,7,11], 8)}")piles [3,6,7,11] in 8 hours → speed 4Recognising these as one problem is the point.
Rotated sorted array
def search_rotated(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target: return mid
if nums[lo] <= nums[mid]: # left half is sorted
if nums[lo] <= target < nums[mid]: hi = mid - 1
else: lo = mid + 1
else: # right half is sorted
if nums[mid] < target <= nums[hi]: lo = mid + 1
else: hi = mid - 1
return -1
rot = [4,5,6,7,0,1,2]
for t in (0, 4, 3):
print(f"search {t} in {rot} → {search_rotated(rot, t)}")search 0 in [4, 5, 6, 7, 0, 1, 2] → 4
search 4 in [4, 5, 6, 7, 0, 1, 2] → 0
search 3 in [4, 5, 6, 7, 0, 1, 2] → -1“At every step at least one half is properly sorted — I identify which by comparing the endpoints, then check whether the target lies inside that sorted half. If it does, search there; otherwise search the other. Still O(log n).”
Heaps
h = []
for x in [5, 2, 8, 1, 9]:
heapq.heappush(h, x)
print(f"heap {h} smallest {h[0]}")
print(f"pop order: {[heapq.heappop(h) for _ in range(5)]}")
# Python only has a MIN-heap. Negate for a max-heap.
maxh = []
for x in [5, 2, 8, 1, 9]:
heapq.heappush(maxh, -x)
print(f"max-heap pops: {[-heapq.heappop(maxh) for _ in range(5)]}")heap [1, 2, 8, 5, 9] smallest 1
pop order: [1, 2, 5, 8, 9]
max-heap pops: [9, 8, 5, 2, 1]Note the heap list is not sorted — only the invariant that each parent is ≤ its children holds. Printing it and expecting sorted output is a common confusion.
heapify is O(n), not O(n log n):
data = [random.random() for _ in range(500_000)]
t0 = time.perf_counter(); h1 = list(data); heapq.heapify(h1); t1 = time.perf_counter()
h2 = []
for x in data: heapq.heappush(h2, x)
t2 = time.perf_counter()
print(f"heapify O(n) {t1-t0:7.4f}s")
print(f"n × heappush O(n lg n) {t2-t1:7.4f}s")heapify O(n) 0.0284s
n × heappush O(n lg n) 0.6412sThe heap-vs-sort crossover
def top_k_sort(nums, k): return sorted(nums, reverse=True)[:k]
def top_k_heap(nums, k): return heapq.nlargest(k, nums)
nums = [random.random() for _ in range(2_000_000)]
print(f"{'k':>9} {'sort':>9} {'heap':>9} winner")
for k in (10, 1_000, 50_000, 200_000, 500_000):
t0 = time.perf_counter(); top_k_sort(nums, k); t1 = time.perf_counter()
top_k_heap(nums, k); t2 = time.perf_counter()
print(f"{k:>9,} {t1-t0:>8.3f}s {t2-t1:>8.3f}s {'heap' if (t2-t1)<(t1-t0) else 'sort'}") k sort heap winner
10 0.842s 0.104s heap
1,000 0.851s 0.142s heap
50,000 0.848s 0.402s heap
200,000 0.844s 0.918s sort
500,000 0.851s 1.284s sort“O(n log k) beats O(n log n) while k is much smaller than n — here up to about k = n/20. Past that, Timsort’s tiny constant in optimised C wins despite the worse complexity. If I did not know k in advance I would sort, because it is simpler and its cost is flat.”
Naming the crossover is a better answer than naming the complexity.
Merging k sorted lists
def merge_k_sorted(lists):
"""O(N log k) — heap holds one element per list, not all N."""
heap = [(lst[0], i, 0) for i, lst in enumerate(lists) if lst]
heapq.heapify(heap)
out = []
while heap:
val, li, idx = heapq.heappop(heap)
out.append(val)
if idx + 1 < len(lists[li]):
heapq.heappush(heap, (lists[li][idx + 1], li, idx + 1))
return out
print(merge_k_sorted([[1,4,7], [2,5,8], [3,6,9]]))
print(merge_k_sorted([[], [1], []]))
print(merge_k_sorted([]))[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1]
[]The tuple carries (value, list_index, element_index) — and the list index is doing double
duty as a tiebreak, which matters when values are equal and the payload is not comparable:
try:
heapq.heappush([], (1, {"a": 1}))
heapq.heappush([(1, {"a": 1})], (1, {"b": 2}))
except TypeError as e:
print(f"dict as tiebreak → TypeError: {e}")dict as tiebreak → TypeError: '<' not supported between instances of 'dict' and 'dict'Always put a comparable tiebreak — an index or a counter — between the sort key and any non-comparable payload.
Quickselect: the k-th element without sorting
def quickselect(nums, k):
"""k-th smallest (0-indexed). Average O(n), worst O(n²)."""
nums = list(nums)
lo, hi = 0, len(nums) - 1
while True:
if lo == hi: return nums[lo]
pivot = nums[random.randint(lo, hi)] # random pivot avoids the sorted worst case
i, j = lo, hi
while i <= j:
while nums[i] < pivot: i += 1
while nums[j] > pivot: j -= 1
if i <= j:
nums[i], nums[j] = nums[j], nums[i]
i, j = i + 1, j - 1
if k <= j: hi = j
elif k >= i: lo = i
else: return nums[k]
data = random.sample(range(100_000), 20_000)
k = 5_000
t0 = time.perf_counter(); a = quickselect(data, k); t1 = time.perf_counter()
b = sorted(data)[k]; t2 = time.perf_counter()
c = heapq.nsmallest(k + 1, data)[-1]; t3 = time.perf_counter()
print(f"quickselect {t1-t0:7.4f}s → {a}")
print(f"sort {t2-t1:7.4f}s → {b}")
print(f"heap {t3-t2:7.4f}s → {c}")quickselect 0.0284s → 24817
sort 0.0041s → 24817
heap 0.0812s → 24817Note sort wins on this size — Timsort’s constant again. Quickselect is the theoretically right answer at O(n) average and the practically right one only at large n with a small constant-factor implementation. Say that rather than presenting it as a straight improvement.
Recognising it
SIGNAL REACH FOR
"sort by X then Y" tuple key, or chained stable sorts
"nearly sorted input" Timsort is already O(n) — say so
"find X in a sorted array" binary search / bisect
"minimum X such that a condition holds" binary search the ANSWER space
"rotated sorted array" modified binary search
"top k", "k largest/closest" heap — check the crossover
"k-th smallest, one query" quickselect (or sort if n is modest)
"merge k sorted things" heap of size k
"running median" two heaps
"schedule / intervals" sort first, then sweepThe checklist
print(binary_search([], 1), binary_search([1], 1), binary_search([1], 2))
print(first_true(0, 0, lambda x: True))
print(merge_k_sorted([[]]), heapq.nlargest(5, [1, 2]))
try:
heapq.heappop([])
except IndexError:
print("heappop on empty → IndexError (guard it)")
print(min_ship_capacity([5], 1))-1 0 -1
0
[] [2, 1]
heappop on empty → IndexError (guard it)
5nlargest(5, [1, 2]) returning two elements rather than raising is worth knowing — it clamps
silently, which is usually what you want and occasionally hides a bug.
Practice
1. Sort already-sorted data and compare with random.
random 0.4102s already sorted 0.0184s22×. Timsort detects existing runs, so “nearly sorted” input is genuinely O(n) — worth mentioning whenever a problem says the data is mostly ordered.
2. Binary search an answer space with nothing sorted.
5 days → capacity 15 (~6 probes over 46 candidates)The feasibility function is monotonic, which is all binary search needs. This variant is what separates candidates on medium-hard problems.
3. Find the heap-vs-sort crossover.
k = 50,000 → heap wins
k = 200,000 → sort winsThe asymptotically better algorithm loses past roughly k = n/20. Naming the crossover beats naming the complexity.
4. Push a tuple with a non-comparable payload onto a heap.
TypeError: '<' not supported between instances of 'dict' and 'dict'Equal keys make the heap compare the payload. Always insert a comparable tiebreak — an index or a counter — between the key and the object.
Next: dynamic programming — recognising overlapping subproblems and writing the recurrence.