Sorting and Searching Algorithms Questions
Comparison and non-comparison sorting (quicksort with its pivot and partition choices and hybrid cutoffs, mergesort, heapsort as a sort, insertion/selection/bubble, counting/radix/bucket), their stability, in-place behavior, stack depth and lower bounds, and choosing a sort from input constraints, including near-sorted data, library sorts (Timsort, introsort, language defaults), comparator design and expensive comparisons or copies. Also selection (quickselect, median-of-medians, nth_element), external merge sorting of data larger than memory (run generation and merge passes), and binary search with its variants: first/last occurrence, lower/upper bound, rotated arrays with or without duplicates, peak and mountain arrays, sorted matrices, unbounded search, loop-invariant correctness and off-by-one pitfalls, and binary search on an answer space (discrete or continuous, including k-th smallest by value). Includes divide-and-conquer reasoning for sorts (merge step, merging sorted arrays, median of two sorted arrays, inversion counting). Excludes heap data-structure mechanics and heap-based top-k and k-way merging, trees and tries, general graph search, distributed data-processing systems, approximate nearest-neighbor and streaming-sketch algorithms, and abstract Big-O comparison.
When is linear search a better choice than binary search? Cover array size, data layout, access cost, unsorted or streaming data, and give two concrete cases for each approach.
Sample Answer
The short answer
Choose linear search (look at items one by one, in order) when the data is small, unsorted, arrives as a stream, can only be walked in order, or the question is not an exact-match question. Choose binary search (repeatedly halve a sorted range) when the data is sorted, supports jumping to any position in constant time, and is searched many times. Binary search needs fewer element reads per search, but it has to pay for being sorted and indexable first, and that price is only worth paying under the right conditions.
The cost model
Everything below counts probes: the number of times an element is read and compared. The program counts probes, not seconds, because wall-clock time depends on the machine.
import bisect
import random
from functools import cmp_to_key
def linear_search(items, target):
"""Return (index or -1, element probes)."""
probes = 0
for i, x in enumerate(items):
probes += 1
if x == target:
return i, probes
return -1, probes
def binary_search(items, target):
lo, hi, probes = 0, len(items) - 1, 0
while lo <= hi:
mid = lo + (hi - lo) // 2
probes += 1
if items[mid] == target:
return mid, probes
if items[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1, probes
# 1. Array size: probes for a target larger than every element (the worst case for both).
print("n linear probes binary probes")
for n in (1, 2, 4, 8, 64, 1000, 1_000_000):
data = list(range(n))
print(f"{n:<11}{linear_search(data, n)[1]:<15}{binary_search(data, n)[1]}")
# 2. Access cost: a singly linked list has no jump to the middle; reaching it means following next pointers.
class Node:
def __init__(self, value, nxt=None):
self.value, self.next = value, nxt
def build_list(values):
head = None
for v in reversed(values):
head = Node(v, head)
return head
def linked_linear(head, target):
hops = 0
while head is not None:
if head.value == target:
return True, hops
head, hops = head.next, hops + 1
return False, hops
def linked_binary(head, n, target, log=None):
"""Binary search on a linked list: every probe walks forward from the start of the window."""
lo, hi, hops, probes = 0, n - 1, 0, 0
lo_node = head
while lo <= hi:
mid = lo + (hi - lo) // 2
probes += 1
node = lo_node
for _ in range(mid - lo):
node, hops = node.next, hops + 1
if node.value == target:
return True, hops, probes
if node.value < target:
lo, lo_node, hops = mid + 1, node.next, hops + 1
else:
hi = mid - 1
if log is not None:
log.append(hops)
return False, hops, probes
print("\nlinked list, n=1000, target absent:")
head = build_list(list(range(1000)))
print(" linear scan: pointer hops =", linked_linear(head, 1000)[1])
hop_log = []
found, hops, probes = linked_binary(head, 1000, 1000, hop_log)
print(f" binary search: pointer hops = {hops}, element comparisons = {probes}")
print(" hops added in each of the", len(hop_log), "rounds:", [b - a for a, b in zip([0] + hop_log, hop_log)])
# 3. Unsorted data: search once with a scan, or sort first and then binary search?
rng = random.Random(42)
n = 1000
data = rng.sample(range(10 ** 6), n)
sort_comparisons = 0
def counting_cmp(a, b):
global sort_comparisons
sort_comparisons += 1
return (a > b) - (a < b)
sorted_data = sorted(data, key=cmp_to_key(counting_cmp))
print(f"\nunsorted n={n}: sorting costs {sort_comparisons} comparisons")
queries = rng.sample(data, 200)
print("queries scan total probes sort + binary total probes")
for q in (1, 5, 10, 20, 50, 200):
scan = sum(linear_search(data, t)[1] for t in queries[:q])
binary = sort_comparisons + sum(binary_search(sorted_data, t)[1] for t in queries[:q])
print(f"{q:<9}{scan:<19}{binary}")
# 4. Streaming data: items arrive once and cannot be revisited or indexed.
stream = (rng.randrange(1000) for _ in range(10 ** 6))
consumed = 0
for value in stream:
consumed += 1
if value > 990:
break
print(f"\nstream: first value above 990 arrived as item {consumed}; memory used by the search is O(1)")
# 5. Compressed storage: sorted ids stored as variable-length deltas have no random access.
def encode_deltas(sorted_ids):
out, prev = bytearray(), 0
for v in sorted_ids:
delta = v - prev
prev = v
while delta >= 128:
out.append(128 | (delta & 127))
delta >>= 7
out.append(delta)
return bytes(out)
def scan_deltas(blob, target):
"""Decode left to right; the data is sorted, so stop as soon as the running value passes target."""
pos, value, shift, delta = 0, 0, 0, 0
while pos < len(blob):
b = blob[pos]
pos += 1
delta |= (b & 127) << shift
if b < 128:
value += delta
if value == target:
return True, pos
if value > target:
return False, pos
shift, delta = 0, 0
else:
shift += 7
return False, pos
def decode_all(blob):
values, value, shift, delta = [], 0, 0, 0
for b in blob:
delta |= (b & 127) << shift
if b < 128:
value += delta
values.append(value)
shift, delta = 0, 0
else:
shift += 7
return values
demo_ids = [5, 130, 300]
demo_deltas = [b - a for a, b in zip([0] + demo_ids, demo_ids)]
print("\ndelta encoding of", demo_ids, "-> deltas", demo_deltas, "-> bytes", list(encode_deltas(demo_ids)))
print(" decoded back:", decode_all(encode_deltas(demo_ids)), "; 170 is 128 + 42 then a second byte 1: 42 + 1 * 128 =", 42 + 1 * 128)
ids = sorted(rng.sample(range(10 ** 5), 1000))
blob = encode_deltas(ids)
print(f"\ncompressed ids: 1000 ids in {len(blob)} bytes")
print(" scan for ids[500] reads", scan_deltas(blob, ids[500])[1], "bytes ->", scan_deltas(blob, ids[500])[0])
print(" the middle byte has the value", blob[len(blob) // 2], "but ids[500] is", ids[500],
"(each stored number is a delta from the one before it)")
# 6. Approximate matching: the order of the keys says nothing about which keys are close.
def within_one_edit(a, b):
if abs(len(a) - len(b)) > 1:
return False
i = 0
while i < min(len(a), len(b)) and a[i] == b[i]:
i += 1
return a[i + 1:] == b[i + 1:] or a[i:] == b[i + 1:] or a[i + 1:] == b[i:]
for x, y in (("cat", "cut"), ("cat", "cart"), ("cart", "cat"), ("cat", "dog")):
print(f"within_one_edit({x!r}, {y!r}) =", within_one_edit(x, y))
words = sorted(["receive", "recipe", "reduce", "refer", "regard", "relax", "remote", "repeat", "result", "retail", "review", "reward"])
query = "xeceive"
near = [w for w in words if within_one_edit(query, w)]
print(f"\napproximate: scanning {len(words)} words for one edit away from {query!r} finds {near}")
print(" bisect would look near index", bisect.bisect_left(words, query), "but the match is at index", words.index("receive"))
The output below is the complete output of that program. In it, bisect is Python's standard-library module for binary search on a sorted list: bisect.bisect_left(words, x) returns the index where x would be inserted to keep the list sorted. Edit distance is the smallest number of single-character insertions, deletions or substitutions that turn one word into another.
n linear probes binary probes
1 1 1
2 2 2
4 4 3
8 8 4
64 64 7
1000 1000 10
1000000 1000000 20
linked list, n=1000, target absent:
linear scan: pointer hops = 1000
binary search: pointer hops = 1000, element comparisons = 10
hops added in each of the 10 rounds: [500, 250, 125, 63, 31, 16, 8, 4, 2, 1]
unsorted n=1000: sorting costs 8645 comparisons
queries scan total probes sort + binary total probes
1 359 8655
5 2126 8691
10 4622 8738
20 8589 8827
50 24815 9084
200 102564 10439
stream: first value above 990 arrived as item 21; memory used by the search is O(1)
delta encoding of [5, 130, 300] -> deltas [5, 125, 170] -> bytes [5, 125, 170, 1]
decoded back: [5, 130, 300] ; 170 is 128 + 42 then a second byte 1: 42 + 1 * 128 = 170
compressed ids: 1000 ids in 1284 bytes
scan for ids[500] reads 645 bytes -> True
the middle byte has the value 78 but ids[500] is 52487 (each stored number is a delta from the one before it)
within_one_edit('cat', 'cut') = True
within_one_edit('cat', 'cart') = True
within_one_edit('cart', 'cat') = True
within_one_edit('cat', 'dog') = False
approximate: scanning 12 words for one edit away from 'xeceive' finds ['receive']
bisect would look near index 12 but the match is at index 0
1. Array size
For a target larger than every element (the worst case for both), the table shows linear search reading all n items and binary search reading about log2 n: 1 and 1 at n = 1, 4 and 3 at n = 4, 8 and 4 at n = 8, 1000 and 10 at n = 1000, and 1,000,000 and 20 at n = 1,000,000. Up to n = 8 the difference is at most 4 reads (8 against 4), and each binary probe also carries bookkeeping (computing mid, branching on the result) while a scan is a simple loop, so on arrays that small the probe count alone does not decide the winner; a real choice at that size should be settled by the other factors below, and by measuring if it matters. As n grows the gap in reads grows with it (64 reads against 7 at n = 64, 1000 against 10 at n = 1000) until it dominates.
2. Data layout and access cost
Binary search assumes random access: reading item mid costs the same wherever mid is. That holds for an array. It fails in two ways:
- A linked list has no jump. To read the middle node you follow
nextpointers from the start of the window. In the program, binary search on a 1000-node list needs 10 element comparisons but still follows 1000 pointers, the same number as the plain scan, because the walks to the successive midpoints add up to roughly n. In each round the code walks from the start of the current window to its middle, then one more step tomid + 1, which becomes the start of the next window. The window halves each round, so the walks halve too; the program prints the hops added in each of the 10 rounds (the list in the output), and they add up to the 1000 shown. Fewer comparisons, no fewer pointer hops. So on a linked list, scan it, or build an index. - Compressed or variable-length storage (each item takes a different number of bytes, so the start of item 500 cannot be computed). The program stores 1000 sorted ids as byte deltas (delta encoding: each stored number is the gap from the previous id, using one or two bytes). Each byte carries 7 bits of the gap in its low bits (
delta & 127), and its top bit is set (128 | ...) when another byte follows;delta >>= 7drops the 7 bits already written. To decode,(b & 127) << shiftputs each 7-bit piece back in place. The small printed example makes this concrete: ids 5, 130, 300 have gaps 5, 125 and 170; 5 and 125 fit in one byte each, and 170 does not, so it is written as 170 (the low 7 bits, 42, plus the top bit 128) followed by the byte 1, which decodes as 42 + 1 x 128 = 170. An id can only be recovered by decoding every delta before it, so there is no way to jump to element 500: the middle byte of the blob has the value 78, which is only a fragment of one gap, while the id at position 500 is 52,487. Scanning with an early stop is what works, and here it read 645 of the 1,284 bytes to findids[500]. Binary search becomes possible again if you keep a small side index holding every k-th id and its byte offset (a skip index), then scan only inside one block.
Contiguous arrays (items stored back to back in memory) also tend to be friendly to a scan: the processor's cache, a small fast memory that loads a whole neighbourhood of addresses at once, already holds the next element, while binary search jumps across memory and misses the cache more often. That cache locality makes small arrays a better fit for scanning than the probe counts alone suggest.
3. Unsorted data
Binary search requires sorted data, and sorting costs O(n log n). The program sorts 1000 random distinct numbers with a counting comparator: 8,645 comparisons. Then it compares total probes for q queries: scanning costs 8,589 probes for 20 queries against 8,827 for sort-plus-binary (the scan is still ahead), and 24,815 against 9,084 for 50 queries (sorting has paid off). So for this array the break-even sits between 20 and 50 queries. If you search once, or a few times, scan. If you search the same data thousands of times, sort once (or keep a hash index, which is a separate alternative to both).
4. Streaming data
A stream delivers each item once and cannot be indexed or revisited, so a binary search has nothing to probe. A scan processes each item as it arrives, stops at the first match (item 21 in the program's stream) and keeps O(1) memory. Sorting a stream first means holding all of it in memory.
Two concrete cases for each approach
Linear search is the right tool when:
- You look up one value in a short unsorted list a single time, for example checking whether a feature name appears in a 20-entry configuration list.
- You read a live log stream for the first line matching a condition, so each line is seen once and in arrival order.
Binary search is the right tool when:
- A sorted array of ten million user ids is loaded once and queried millions of times, so the one-time cost of keeping it sorted is spread across the queries.
- You need the position of a timestamp in a sorted array of events, for example the first event at or after a given time (the boundary of a time range), where an exact match is not even required.
Other cases where linear search wins
- Linked lists: described above (section 2).
- Compressed storage: described above (section 2).
- Approximate matching. Binary search needs a total order (any two keys can be compared and the sorted order is consistent) in which "closer" means "nearby in the array". Edit-distance matching has no such order. The function
within_one_editskips the shared leading characters, then checks the three ways one edit can fix the rest: replace one character (a[i + 1:] == b[i + 1:]), delete one fromb(a[i:] == b[i + 1:]) or delete one froma(a[i + 1:] == b[i:]); the four printedwithin_one_editlines show a substitution, an insertion, a deletion and a clear miss. The program scans 12 sorted words for anything one edit away fromxeceive(a typo ofreceivein its first letter) and findsreceive;bisecton the sorted words would land at index 12, while the match is at index 0, because alphabetical order says nothing about similarity of the rest of the word. For approximate matches use a scan with a distance function, or a structure built for it (such as a BK-tree, a tree whose branches are labelled by edit distance so that a query can skip parts of the tree), not a binary search.
How to decide
- Is it sorted, or will you sort it once and query it many times? If no, scan.
- Can you read any position in constant time (an array, not a list or a decoded stream)? If no, scan, or add an index.
- Is the query an exact match or a boundary on the same sort order? If it is fuzzy or by another key, scan or use another structure.
- Is n large enough that log2 n matters (hundreds or more)? If n is tiny, either works; prefer the simpler scan.
Running the code
docker run --rm -v "$PWD":/w -w /w python:3.12 python search_cost_demo.py
Save the program as search_cost_demo.py. It uses only the standard library, uses fixed seeds, and the output above is from Python 3.12.
Implement selection sort in C++ to sort an array of integers in place. Do not use library sort functions. Provide complexity analysis and explain one scenario where selection sort might be preferable despite O(n^2) time.
Sample Answer
Direct answer
Selection sort splits the array into a sorted prefix (at the front) and an unsorted rest. On each pass it scans the unsorted rest to find the smallest value, then swaps it into the first unsorted slot. It runs in O(n^2) time (always exactly n(n-1)/2 comparisons), uses O(1) extra space, and performs at most n-1 swaps. That small, bounded number of writes is the one scenario where it can beat the other quadratic sorts: when writing to the array is far more expensive than reading it (for example flash memory, a kind of storage whose cells wear out after a limited number of rewrites, or records that are large to move).
The idea in plain words
Imagine laying cards face up and repeatedly picking the smallest remaining card to place next in a new row. Selection sort does the same inside the array, so it needs no second row. The invariant (a statement that is true before and after every pass) is: after pass i, positions 0 to i hold the i+1 smallest values, in sorted order, and they never move again.
Terms used below: in place means the sort needs only a constant amount of extra memory besides the array. Stable means that items with equal keys keep their original relative order.
Approach
- For i from 0 to n-2: assume the minimum of a[i..n-1] is at index i.
- Scan j from i+1 to n-1; whenever a[j] is smaller than the current minimum, remember j.
- If the remembered index is not i, swap a[i] with it.
- The last element needs no pass: once n-1 values are in place, the final one must be the largest.
The algorithm on its own
This is the whole sort, for int values, with nothing else around it:
#include <iostream>
#include <utility>
#include <vector>
void selection_sort(std::vector<int>& a) {
for (std::size_t i = 0; i + 1 < a.size(); ++i) { // i is the first slot not yet sorted
std::size_t min_index = i; // where the smallest value seen so far sits
for (std::size_t j = i + 1; j < a.size(); ++j)
if (a[j] < a[min_index]) min_index = j;
std::swap(a[i], a[min_index]); // put that smallest value into slot i
}
}
int main() {
std::vector<int> a = {29, 10, 14, 37, 13};
selection_sort(a);
for (int x : a) std::cout << x << ' ';
std::cout << '\n';
}
Compiled the same way as the program further down (g++ -std=c++17 -O2 -Wall), it prints:
10 13 14 29 37
Line by line: the outer loop picks the slot i that is about to receive the next smallest value. min_index starts as i itself. The inner loop looks at every later slot j and moves min_index whenever it finds something smaller. After the inner loop, std::swap exchanges slot i with the smallest value found. The outer loop stops at i + 1 < a.size() because the last slot is correct once all earlier ones are.
Code
The program below wraps those same few lines in scaffolding so it can count work and test several element types. The sorting loop in it is the one above, plus counters and a skipped swap when the minimum is already in place; everything else is for measuring and checking:
template <typename T, typename Less>makes one function work for any element typeTand any comparison functionLess, so the same code sortsintvalues andTaggedrecords.[](int x, int y) { return x < y; }is a lambda, an inline function with no name; it is passed in asless, the rule for "comes before".Statsholds three counters (comparisons, swaps, array writes) that the sort increments as it works.if constexpr (std::is_arithmetic_v<T>)is a check done when the program is compiled: the trace line is printed only whenTis a number type, because aTaggedrecord has no<<printing.std::mt19937 rng(42)is a random number generator with a fixed seed, so the shuffled test arrays are the same on every run.
selection_sort is a template so the same function sorts integers and tagged records. It returns counts of comparisons, swaps and array-slot writes, taken from the function that does the sorting. insertion_sort appears only to compare the number of writes. The driver prints the array after every pass, runs the edge cases, tests stability with tagged equal keys, and checks 500 random arrays with many duplicates against std::sort.
#include <algorithm>
#include <cstddef>
#include <iomanip>
#include <iostream>
#include <random>
#include <type_traits>
#include <vector>
struct Stats {
long comparisons = 0;
long swaps = 0;
long writes = 0; // array slots assigned
};
// In-place selection sort. After pass i, a[0..i] holds the i+1 smallest values in order.
template <typename T, typename Less>
Stats selection_sort(std::vector<T>& a, Less less, bool trace = false) { // trace needs T printable
Stats s;
const std::size_t n = a.size();
for (std::size_t i = 0; i + 1 < n; ++i) {
std::size_t min_index = i;
for (std::size_t j = i + 1; j < n; ++j) {
++s.comparisons;
if (less(a[j], a[min_index])) min_index = j;
}
if (min_index != i) { // skip the swap when the minimum is already in place
std::swap(a[i], a[min_index]);
++s.swaps;
s.writes += 2;
}
if constexpr (std::is_arithmetic_v<T>) if (trace) {
std::cout << "after pass " << i + 1 << " (picked index " << min_index << "): ";
for (const T& x : a) std::cout << x << ' ';
std::cout << '\n';
}
}
return s;
}
// Insertion sort, shipped only to compare the number of array writes.
template <typename T, typename Less>
Stats insertion_sort(std::vector<T>& a, Less less) {
Stats s;
for (std::size_t i = 1; i < a.size(); ++i) {
T key = a[i];
std::size_t j = i;
while (j > 0) {
++s.comparisons;
if (!less(key, a[j - 1])) break;
a[j] = a[j - 1];
++s.writes;
--j;
}
a[j] = key;
++s.writes;
}
return s;
}
struct Tagged {
int key;
char tag;
};
int main() {
auto int_less = [](int x, int y) { return x < y; };
std::vector<int> demo = {29, 10, 14, 37, 13};
std::cout << "start: 29 10 14 37 13\n";
Stats s = selection_sort(demo, int_less, true);
std::cout << "comparisons=" << s.comparisons << " swaps=" << s.swaps << "\n\n";
// Edge cases
std::vector<int> empty, one = {7}, equal = {5, 5, 5}, sorted = {1, 2, 3, 4};
for (auto* v : {&empty, &one, &equal, &sorted}) {
Stats e = selection_sort(*v, int_less);
std::cout << "size " << v->size() << ": comparisons=" << e.comparisons
<< " swaps=" << e.swaps << '\n';
}
// Stability test with tagged equal keys: 3a, 3b, 1c -> a stable sort gives 1c 3a 3b
std::vector<Tagged> t = {{3, 'a'}, {3, 'b'}, {1, 'c'}};
selection_sort(t, [](const Tagged& x, const Tagged& y) { return x.key < y.key; });
std::cout << "\ntagged result: ";
for (auto& x : t) std::cout << x.key << x.tag << ' ';
std::cout << " (stable would be 1c 3a 3b)\n";
// Counts for n = 8 and n = 16 on one fixed random permutation each, plus the write comparison
std::mt19937 rng(42);
std::cout << "\n n selection(cmp,swaps,writes) insertion(cmp,writes) n(n-1)/2 n-1\n";
for (std::size_t n : {8, 16, 32, 64}) {
std::vector<int> base(n);
for (std::size_t i = 0; i < n; ++i) base[i] = static_cast<int>(i);
std::shuffle(base.begin(), base.end(), rng);
std::vector<int> a = base, b = base, ref = base;
Stats sa = selection_sort(a, int_less);
Stats sb = insertion_sort(b, int_less);
std::sort(ref.begin(), ref.end());
if (a != ref || b != ref) { std::cout << "MISMATCH\n"; return 1; }
std::cout << std::setw(3) << n << " " << sa.comparisons << "," << sa.swaps << "," << sa.writes
<< " | " << sb.comparisons << "," << sb.writes << " | "
<< n * (n - 1) / 2 << " " << n - 1 << '\n';
}
// Randomised check against std::sort, with duplicates
std::uniform_int_distribution<int> val(0, 9), len(0, 12);
for (int trial = 0; trial < 500; ++trial) {
std::vector<int> v(len(rng));
for (auto& x : v) x = val(rng);
std::vector<int> ref = v;
std::sort(ref.begin(), ref.end());
selection_sort(v, int_less);
if (v != ref) { std::cout << "FAIL\n"; return 1; }
}
std::cout << "500 random arrays with duplicates match std::sort\n";
return 0;
}
Compiled with g++ 14.2 (g++ -std=c++17 -O2 -Wall), it prints:
start: 29 10 14 37 13
after pass 1 (picked index 1): 10 29 14 37 13
after pass 2 (picked index 4): 10 13 14 37 29
after pass 3 (picked index 2): 10 13 14 37 29
after pass 4 (picked index 4): 10 13 14 29 37
comparisons=10 swaps=3
size 0: comparisons=0 swaps=0
size 1: comparisons=0 swaps=0
size 3: comparisons=3 swaps=0
size 4: comparisons=6 swaps=0
tagged result: 1c 3b 3a (stable would be 1c 3a 3b)
n selection(cmp,swaps,writes) insertion(cmp,writes) n(n-1)/2 n-1
8 28,5,10 | 23,24 | 28 7
16 120,12,24 | 92,95 | 120 15
32 496,29,58 | 278,282 | 496 31
64 2016,58,116 | 1117,1119 | 2016 63
500 random arrays with duplicates match std::sort
Reading the trace
Starting from 29 10 14 37 13:
- Pass 1 scans four candidates, finds 10 at index 1, swaps it with the 29 at index 0.
- Pass 2 finds 13 at index 4 and swaps it into index 1.
- Pass 3 finds that 14 is already at index 2, so no swap happens (this is the
min_index != icheck). - Pass 4 compares 37 with 29, finds 29 at index 4 and swaps.
Comparisons: 4 + 3 + 2 + 1 = 10. Swaps: 3, fewer than the maximum n-1 = 4 because pass 3 needed none.
Complexity, with the reason
- Time: the inner loop runs n-1, n-2, ..., 1 times, so comparisons are always n(n-1)/2 whatever the input. The table confirms it: 28, 120, 496 and 2016 for n = 8, 16, 32 and 64, on random permutations. Doubling n roughly quadruples the comparisons. Even an already sorted array costs the full count (the
size 4row shows 6 comparisons, no swaps), so there is no early exit and no best case better than O(n^2). - Swaps and writes: at most one swap per pass, so at most n-1 swaps and 2(n-1) slot writes. The table shows 116 writes for n = 64, against 1119 for insertion sort on the same permutation.
- Space: O(1): two indices and a swap temporary, and no recursion.
Edge cases and common mistakes
- Empty and one-element arrays: the outer loop
i + 1 < nnever runs (the size 0 and size 1 rows show 0 comparisons). Writing the bound asi < n - 1with an unsignednunderflows whennis 0 in C++, which is why the code usesi + 1 < n. - All-equal input: strict
<means the minimum index never moves, so no swaps happen (the size 3 row). - Duplicates in general: handled, as the 500 random arrays over only ten distinct values show.
- The sort is not stable. The tagged test sorted
3a 3b 1cinto1c 3b 3a: the first swap moved 1c to the front by exchanging it with 3a, and 3a jumped past 3b. Making it stable means shifting elements instead of swapping, which costs O(n) writes per pass and removes the property that makes the sort attractive. - Mistakes to avoid: swapping inside the inner loop every time a smaller value is seen (that makes O(n^2) swaps, which is bubble-sort-like behaviour), and storing the minimum value but not its index.
When selection sort is the right choice despite O(n^2)
Pick it when writes are the scarce resource and the array is small enough that quadratic reads are acceptable. Examples: sorting records stored in flash or EEPROM (a small rewritable memory chip common in embedded devices) where every write wears the cell, or sorting a few dozen large structs whose move costs far more than a comparison. It does at most n-1 swaps, where insertion sort did 1119 writes and selection 116 at n = 64. For large n, or when stability matters, prefer merge sort or a library sort, which are O(n log n).
When should you use your language's built-in sort instead of writing a custom one? Cover performance, stability, comparator correctness and maintainability, and describe how you would evaluate replacing an existing hand-written sort in a production codebase.
Sample Answer
Direct answer
Use the language's built-in sort by default. It is already correct on the awkward inputs, it is maintained by people who test it far more than your team can, and it is usually the fastest option you can write without special knowledge of your data. Check what your language promises about equal keys: Python's sorted and list.sort and Java's Arrays.sort on objects are guaranteed stable (equal keys keep their input order), while C++ std::sort does not preserve the order of equivalent elements and std::stable_sort does. Write a custom sort only when you can name the property of your data that a general sort cannot use (a small integer range, nearly sorted input, only the top few items needed, data too big for memory) and have measured a gain that matters. If a hand-written sort already exists in production, replace it behind a shadow comparison: run the old and the new sort side by side on real inputs without serving the new result, compare the outputs including the order of equal keys, then roll out gradually with a way back.
The idea in plain words
A sort has four properties that matter: how many comparisons it makes (performance), whether equal keys stay in input order (stability), whether the ordering rule given to it is consistent (comparator correctness: a comparator is the function that decides which of two items goes first), and whether someone can still read and maintain it. A hand-written sort has to get all four right; the built-in has done so for years.
Two terms of quicksort appear in the code. The pivot is the element every other item is compared against. Partitioning is splitting the remaining items into those that go before the pivot and those that go after it, then sorting each side the same way. hand_quicksort takes the first element as the pivot. On input that is already in order, every other item is larger than the pivot, so one side is always empty and each call removes just one item.
What the built-in gives you, shown with numbers
The program counts comparisons (never time) and has six numbered sections. Section 0 prints every pivot and partition of the first-element-pivot quicksort on four sorted items. Section 1 scales that to 500 items against sorted(). Section 2 is a comparator bug, section 3 is descending order with ties, section 4 is the number of calls made by key= versus a comparator, and section 5 is the shadow check that the evaluation plan below relies on. Counted counts every <, cmp_to_key adapts an old-style two-argument comparator, and key= supplies one sort value per item.
import random
from functools import cmp_to_key
class Counted:
"""Wraps a value and counts every `<` comparison made on it."""
calls = 0
def __init__(self, value):
self.value = value
def __lt__(self, other):
Counted.calls += 1
return self.value < other.value
def count_comparisons(sort_function, values):
Counted.calls = 0
sort_function([Counted(v) for v in values])
return Counted.calls
def hand_quicksort(items):
"""The kind of hand-written sort found in old code: first element is the pivot."""
if len(items) <= 1:
return items
pivot, rest = items[0], items[1:]
smaller, larger = [], []
for x in rest: # one comparison per element
(smaller if x < pivot else larger).append(x)
return hand_quicksort(smaller) + [pivot] + hand_quicksort(larger)
def show_partitions(items, depth=0):
"""Print each call of the first-element-pivot sort: the pivot and the two sides it creates."""
if len(items) <= 1:
return
pivot, rest = items[0], items[1:]
smaller = [x for x in rest if x < pivot]
larger = [x for x in rest if not x < pivot]
print(" " + " " * depth + f"pivot {pivot}: smaller {smaller}, larger {larger}, {len(rest)} comparisons")
show_partitions(smaller, depth + 1)
show_partitions(larger, depth + 1)
def unstable_in_place_sort(records, key):
"""Hand-written selection sort: correct order, but swaps can reorder ties."""
for i in range(len(records)):
smallest = min(range(i, len(records)), key=lambda j: key(records[j]))
records[i], records[smallest] = records[smallest], records[i]
return records
def shadow_check(candidate, reference, cases, key):
"""Compare a sort against the reference on many inputs; report order errors and tie-order differences."""
order_errors = tie_differences = 0
for case in cases:
got, want = candidate(list(case)), reference(list(case))
if [key(r) for r in got] != [key(r) for r in want]:
order_errors += 1
elif got != want:
tie_differences += 1
return order_errors, tie_differences
if __name__ == "__main__":
print("0. the first-element pivot on 4 sorted items")
show_partitions([0, 1, 2, 3])
print(" comparisons:", count_comparisons(hand_quicksort, [0, 1, 2, 3]))
n = 500
ordered = list(range(n))
print("1. comparisons on", n, "already-sorted items")
print(" hand_quicksort :", count_comparisons(hand_quicksort, ordered))
print(" sorted() :", count_comparisons(sorted, ordered))
print(" n*(n-1)/2 :", n * (n - 1) // 2)
try:
hand_quicksort(list(range(2000)))
except RecursionError:
print(" hand_quicksort on 2000 sorted items: RecursionError (default limit 1000)")
print(" sorted() on 2000 sorted items:", sorted(range(2000))[-1], "(last item)")
print("2. comparator bug: int(a - b) on floats")
prices = [0.9, 0.5, 0.2, 0.7]
print(" cmp_to_key(int(a-b)):", sorted(prices, key=cmp_to_key(lambda a, b: int(a - b))))
print(" sorted(prices) :", sorted(prices))
print("3. descending order and ties (record = (score, arrival))")
rows = [(2, "a"), (1, "b"), (2, "c"), (1, "d")]
print(" sorted(reverse=True) :", sorted(rows, key=lambda r: r[0], reverse=True))
print(" ascending then .reverse() :", list(reversed(sorted(rows, key=lambda r: r[0]))))
print("4. key= versus cmp_to_key on 1,000 random numbers")
rng = random.Random(5)
data = [rng.random() for _ in range(1000)]
key_calls = cmp_calls = 0
def counting_key(x):
global key_calls
key_calls += 1
return x
def counting_cmp(a, b):
global cmp_calls
cmp_calls += 1
return (a > b) - (a < b)
sorted(data, key=counting_key)
sorted(data, key=cmp_to_key(counting_cmp))
print(" key function calls:", key_calls, " comparator calls:", cmp_calls)
print("5. shadow check against sorted() on 200 tagged cases")
rng = random.Random(9)
cases = [[(rng.randint(0, 5), i) for i in range(rng.randint(0, 12))] for _ in range(200)]
by_score = lambda r: r[0]
reference = lambda recs: sorted(recs, key=by_score)
coarse = lambda recs: sorted(recs, key=lambda r: r[0] // 2) # a typical slip: wrong key
print(" selection sort (order errors, tie differences):",
shadow_check(lambda recs: unstable_in_place_sort(recs, by_score), reference, cases, by_score))
print(" coarse key (order errors, tie differences):", shadow_check(coarse, reference, cases, by_score))
print(" control: sorted() (order errors, tie differences):", shadow_check(reference, reference, cases, by_score))
Output (python:3.12):
0. the first-element pivot on 4 sorted items
pivot 0: smaller [], larger [1, 2, 3], 3 comparisons
pivot 1: smaller [], larger [2, 3], 2 comparisons
pivot 2: smaller [], larger [3], 1 comparisons
comparisons: 6
1. comparisons on 500 already-sorted items
hand_quicksort : 124750
sorted() : 499
n*(n-1)/2 : 124750
hand_quicksort on 2000 sorted items: RecursionError (default limit 1000)
sorted() on 2000 sorted items: 1999 (last item)
2. comparator bug: int(a - b) on floats
cmp_to_key(int(a-b)): [0.9, 0.5, 0.2, 0.7]
sorted(prices) : [0.2, 0.5, 0.7, 0.9]
3. descending order and ties (record = (score, arrival))
sorted(reverse=True) : [(2, 'a'), (2, 'c'), (1, 'b'), (1, 'd')]
ascending then .reverse() : [(2, 'c'), (2, 'a'), (1, 'd'), (1, 'b')]
4. key= versus cmp_to_key on 1,000 random numbers
key function calls: 1000 comparator calls: 8653
5. shadow check against sorted() on 200 tagged cases
selection sort (order errors, tie differences): (0, 86)
coarse key (order errors, tie differences): (122, 0)
control: sorted() (order errors, tie differences): (0, 0)
Reading the output
- The pivot by hand. For
[0, 1, 2, 3]the first call compares the 3 remaining items with pivot 0 and all 3 land in the larger side, the next call compares 2 items with pivot 1, the next 1 item with pivot 2: 3 + 2 + 1 = 6 comparisons, which is 4 x 3 / 2. In general the sum (n-1) + (n-2) + ... + 1 equals n(n-1)/2, which is the number in the next item. - Performance on awkward input. On 500 already-sorted items the hand-written quicksort makes 124,750 comparisons, which is exactly n(n-1)/2, because choosing the first element as the pivot makes every partition peel off one item. The built-in
sorted()makes 499, n-1, because Timsort (Python's sort, which finds runs that are already in order) detects the sorted run. The hand-written version also has a recursion depth equal to n for this input, and at 2,000 items it hits Python's default limit of 1,000 and raisesRecursionError, whilesorted()returns normally. Its worst case is O(n^2) for this pivot rule, on input that is common in practice. - Comparator correctness.
cmp_to_key(lambda a, b: int(a - b))turns every difference smaller than 1 into 0, so all four prices count as equal and come back as[0.9, 0.5, 0.2, 0.7], unsorted. Preferkey=, which returns a value to sort by and cannot be inconsistent. If a comparator is unavoidable, return(a > b) - (a < b). - Stability and descending order.
sorted(..., reverse=True)keeps equal keys in input order ((2, 'a')before(2, 'c')), while sorting ascending and then reversing the list flips them. If a downstream consumer relies on the order of ties, that difference is visible. - Allocation and call counts.
key=is called once per element (1,000 calls for 1,000 numbers), whilecmp_to_keycalls the comparator 8,653 times on the same data because it is called per comparison.sorted()allocates a new list of n slots;list.sort()sorts in place. Because the key function runs once per element, an allocating key function costs one allocation per element, not one per comparison.
When a custom sort is justified
| Situation | Better than a general comparison sort | Reason |
|---|---|---|
| Integers in a small known range | counting sort (tally how many times each value occurs, then write the values out in order) or radix sort (sort digit by digit with a counting sort per digit) | uses the value as an index, O(n + range) |
| Only the best k of n are needed | heapq.nsmallest / nlargest (standard-library functions that keep a heap of k items) or quickselect (partition like quicksort, then continue into only the side that holds the wanted rank) | no need to order the rest |
| Data already almost sorted | keep the built-in | Timsort exploits existing runs (499 comparisons above) |
| Data larger than memory | external merge sort (sort memory-sized chunks, write each to disk, then merge the sorted chunks) | sort chunks, then merge |
| A whole numeric column, sorting is the measured bottleneck | a vectorized library (NumPy, which applies one operation to a whole array in compiled code) or a GPU sort | avoids per-element Python objects; adopt only after profiling |
| Sorting records by several fields | key= returning a tuple, or stable passes | built-in is stable |
In interviews the expected answer is that the built-in is the default and that top-k selection and counting sort are the standard exceptions with their reasons; external merge sort, vectorized sorting and GPU sorting are deeper material that matters mainly for data-heavy roles.
Evaluating the replacement of an existing hand-written sort
The program's section 5 shows the core of the method: a candidate sort is run on 200 tagged random cases and compared with the reference sorted(), separating two kinds of difference. Order errors mean the keys come out in the wrong order. Tie differences mean the keys are right but equal keys appear in another order. The selection sort has 0 order errors but 86 tie differences, the coarse-key mistake has 122 order errors, and the control (the reference against itself) has none of either.
A plan that matches this:
- Pin current behaviour. Write characterization tests (tests that record what the old code does today) for empty input, one item, duplicates, already sorted, reversed,
Noneor missing fields, and the order of ties. Add one test for every bug the old sort ever had. - Decide what is allowed to change. If the old sort was unstable and downstream code accidentally depends on its tie order, the stable built-in will change outputs even though both are "correct". Find those consumers by searching the call sites, then decide, in writing, whether the new tie order is the contract.
- Shadow run. In production or on recorded production inputs, run old and new on the same input (a shadow run: the new sort's result is checked and logged, never served), compare outputs, and log mismatches by kind (order error versus tie difference) without serving the new result.
- Measure. Compare comparison counts, peak memory and tail latency (how long the slowest few percent of requests take, for example the 99th percentile) on real input sizes, and record the numbers.
- Roll out behind a flag. Canary (send the new path to a small share of traffic first, so a fault shows before it reaches everyone) to a small share of traffic, watch error and latency metrics, keep the old path until a full cycle of normal traffic has passed, and keep the rollback one flag flip away.
- Delete the old code. Once the flag is permanent, removing the old sort and its tests is part of the change.
Edge cases and common mistakes
- Using
cmp_to_keyfor somethingkey=can express, paying a comparator call per comparison. - Reaching for a negated key to sort descending: it works for numbers only, while
reverse=Trueworks for any key; both keep ties in input order. - Treating "faster" claims as settled without counting operations or measuring on the real input shape.
- Replacing a sort without checking who depended on its tie order.
- Rewriting a working, tested sort purely for style.
Running the code
python:3.12, standard library only
save the code above as sort_review.py
python sort_review.py
You are choosing a sort for a library that orders variable-length records by timestamp. It must be stable, have low tail latency, and be memory-efficient on 64-bit Linux. Compare Timsort, merge sort, in-place quicksort and radix sort and recommend one.
Sample Answer
Direct answer
Recommend a stable merge-based sort (Timsort, which is what Python's list.sort and sorted use, and, as the Java 21 documentation for Arrays.sort(Object[]) states, a stable, adaptive, iterative merge sort adapted from Tim Peters's list sort, which is what Java uses for object arrays; Java's primitive int[] sorts use a dual-pivot quicksort instead, which is not an option when records must stay in order) over fixed-size entries of the form (timestamp, record offset), not over the variable-length records themselves. The records stay where they are in memory or on disk; only the 16-byte entries (an 8-byte timestamp and an 8-byte offset, on 64-bit Linux) are sorted, and the output is read through the offsets. Timsort is stable, has an O(n log n) worst case (a bounded tail), is adaptive (fully ordered timestamps cost n - 1 comparisons, and nearly ordered ones a small multiple of n: 4313 for n = 2000 when 1% of the entries are out of place, in the output below), and needs at most half the data size as scratch space. Radix sort is the alternative to switch to when timestamps arrive in random order, n is large, and a full scratch buffer is acceptable. Plain in-place quicksort is the one to rule out: it is not stable by default and its worst case is quadratic for the pivot rule shown here.
The idea in plain words
The four candidates differ on three things the question names: whether equal timestamps keep their input order (stable), how bad the slowest run can get (tail latency, which here means the worst-case work, not the average), and how much extra memory is needed beyond the data. Variable-length records make moving the records themselves expensive (each move copies a different number of bytes), so sort a fixed-width handle for each record instead: it is cheap to swap and cheap to compare.
Terms: a run is a stretch of the input that is already in order (Timsort finds runs by walking the input once and comparing neighbours, which costs n - 1 comparisons and then merges the runs; on already sorted input there is one run and nothing to merge); adaptive means the sort does less work when the input contains long runs; pivot is the value quicksort splits the data around; a Lomuto partition is the simple way to split: scan the range once, move every item smaller than the pivot to the front, then put the pivot right after them; heapsort is an O(n log n) sort that keeps the data in a binary heap and repeatedly removes the largest item; median of three uses the middle value of the first, middle and last items as the pivot.
Two mechanisms on small data
Run detection, the idea behind Timsort's speed on logs: one pass over the neighbours splits the input into ascending runs, and merging a few long runs is cheap.
data = [1, 2, 3, 7, 8, 4, 5, 9]
runs, cur = [], [data[0]]
for prev, x in zip(data, data[1:]):
if x >= prev:
cur.append(x)
else:
runs.append(cur); cur = [x]
runs.append(cur)
print("input:", data)
print("ascending runs found with n - 1 =", len(data) - 1, "neighbour comparisons:", runs)
Output (python:3.12):
input: [1, 2, 3, 7, 8, 4, 5, 9]
ascending runs found with n - 1 = 7 neighbour comparisons: [[1, 2, 3, 7, 8], [4, 5, 9]]
LSD radix sort (least significant digit first) sorts by one byte per pass. A pass counts how many keys have each byte value, turns the counts into a start slot per value (the number of keys with a smaller byte value), then deals the keys in input order into their slots. Keys are processed from the lowest byte to the highest, and each pass keeps the order of equal bytes, so the lower bytes break ties for the higher ones. In the shipped code, count = [0] * 257 has one spare slot so that count[digit + 1] can hold the count of digit and the running total then turns count[digit] into that digit's start slot; a byte is skipped when every key shares it (max(count) == len(pairs)). A two-pass example on four keys:
keys = [0x0201, 0x0102, 0x0101, 0x0002]
print("keys (hex):", [f"{k:04x}" for k in keys])
for shift in (0, 8):
digits = [(k >> shift) & 255 for k in keys]
count = [0] * 257
for d in digits:
count[d + 1] += 1 # slot d+1 counts digit d
for d in range(256):
count[d + 1] += count[d] # now count[d] = number of keys with a smaller digit
print(f"pass {shift // 8}: digits {digits}; start slot of each digit used:",
{d: count[d] for d in sorted(set(digits))})
out = [None] * len(keys)
for k in keys:
d = (k >> shift) & 255
out[count[d]] = k
count[d] += 1
keys = out
print(" after the pass:", [f"{k:04x}" for k in keys])
Output (python:3.12):
keys (hex): ['0201', '0102', '0101', '0002']
pass 0: digits [1, 2, 1, 2]; start slot of each digit used: {1: 0, 2: 2}
after the pass: ['0201', '0101', '0102', '0002']
pass 1: digits [2, 1, 1, 0]; start slot of each digit used: {0: 0, 1: 1, 2: 3}
after the pass: ['0002', '0101', '0102', '0201']
In pass 0 the low bytes are 1, 2, 1, 2, so digit 1 starts at slot 0 and digit 2 at slot 2, and the two keys with equal low byte keep their input order (0201 before 0101, 0102 before 0002). Pass 1 looks at the high byte and the keys come out in order.
Comparison
| Sort | Stable | Worst-case work | Extra memory | Adapts to ordered input |
|---|---|---|---|---|
| Timsort | yes | O(n log n) | up to n/2 entries (CPython's listsort notes) | yes |
| Merge sort (shipped below) | yes | O(n log n) | n entries | somewhat (10864 vs 19462 comparisons here, a 44% drop, against 90% for Timsort: 1999 vs 19239) |
| Quicksort, in place | no, unless the index is part of the key | O(n^2) for the pivot rule shipped below | O(log n) stack, with the smaller side handled first | no |
| LSD radix sort | yes | O(passes * n), passes fixed by key width | n entries plus 256 counters | no |
For 10 million records the entries take 10,000,000 * 16 bytes = 160 MB. Timsort's scratch space is at most 80 MB, merge sort and radix need 160 MB, and quicksort needs none. These are arithmetic on the entry size, not measurements.
Code
The entry classes count every < call, so the table below is tallied by the real sorts. ByTsIdx compares the timestamp and then the original index; ByTs compares the timestamp only and is used to show which algorithms keep ties in order without help. The quicksort pivot rule is the last element of the range, with a Lomuto partition, and an explicit stack that always continues with the smaller side.
import random
class ByTs:
"""Sort entry compared on the timestamp only. Counts every '<' call."""
__slots__ = ("ts", "i")
calls = 0
def __init__(self, ts, i):
self.ts, self.i = ts, i
def __lt__(self, other):
ByTs.calls += 1
return self.ts < other.ts
class ByTsIdx(ByTs):
"""Same entry, but ties on the timestamp are broken by the original record index."""
__slots__ = ()
def __lt__(self, other):
ByTs.calls += 1
return (self.ts, self.i) < (other.ts, other.i)
def merge_sort(a):
"""Stable top-down merge sort over index ranges (no slicing). One buffer of len(a) entries."""
buf = [None] * len(a)
def sort(lo, hi):
if hi - lo < 2:
return
mid = (lo + hi) // 2
sort(lo, mid)
sort(mid, hi)
i, j = lo, mid
for k in range(lo, hi):
if j >= hi or (i < mid and not (a[j] < a[i])): # take the left item unless right is strictly smaller
buf[k] = a[i]; i += 1
else:
buf[k] = a[j]; j += 1
for k in range(lo, hi): # copy back without slicing (no temporary list)
a[k] = buf[k]
sort(0, len(a))
return a
def quicksort(a):
"""In-place quicksort, pivot = LAST element of the range (Lomuto partition).
Explicit stack; the larger side is pushed and the smaller side is looped on, so the stack holds
at most about log2(n) ranges. Returns the deepest stack seen.
"""
stack, deepest = [(0, len(a) - 1)], 1
while stack:
lo, hi = stack.pop()
while lo < hi:
pivot, store = a[hi], lo
for j in range(lo, hi):
if a[j] < pivot:
a[j], a[store] = a[store], a[j]
store += 1
a[store], a[hi] = a[hi], a[store]
if store - lo < hi - store:
stack.append((store + 1, hi)); hi = store - 1
else:
stack.append((lo, store - 1)); lo = store + 1
deepest = max(deepest, len(stack))
return deepest
def radix_sort(pairs):
"""LSD radix sort of (timestamp, index) pairs, 8 bits per pass, stable. Skips a byte if all items share it.
Returns (sorted list, number of passes actually run). No comparisons between keys are made."""
passes = 0
for shift in range(0, 64, 8):
count = [0] * 257
for ts, _ in pairs:
count[((ts >> shift) & 255) + 1] += 1
if max(count) == len(pairs):
continue
for d in range(256):
count[d + 1] += count[d]
out = [None] * len(pairs)
for item in pairs: # front to back keeps equal digits in order
d = (item[0] >> shift) & 255
out[count[d]] = item; count[d] += 1
pairs, passes = out, passes + 1
return pairs, passes
def run(name, sorter, cls, stamps):
entries = [cls(ts, i) for i, ts in enumerate(stamps)]
ByTs.calls = 0
extra = sorter(entries)
return entries, ByTs.calls, extra
if __name__ == "__main__":
rng = random.Random(11)
N, BASE = 2000, 1_760_000_000_000 # epoch milliseconds, about 41 bits
random_ts = [BASE + rng.randrange(10**9) for _ in range(N)]
nearly = sorted(random_ts)
for _ in range(N // 100): # move 1% of entries to a random place
nearly.insert(rng.randrange(N), nearly.pop(rng.randrange(N)))
inputs = {
"random": random_ts,
"already sorted": sorted(random_ts),
"1% moved": nearly,
"reversed": sorted(random_ts, reverse=True),
"50 distinct stamps": [BASE + rng.randrange(50) for _ in range(N)],
}
print(f"comparisons for n = {N} (radix: passes of 8 bits, and zero comparisons)")
print(f" {'input':<20}{'list.sort':>10}{'merge sort':>12}{'quicksort':>11}{' radix passes':>15} quicksort stack")
for name, ts in inputs.items():
ref = sorted(range(N), key=lambda i: (ts[i], i))
e1, c1, _ = run("tim", lambda e: e.sort(), ByTsIdx, ts)
e2, c2, _ = run("merge", merge_sort, ByTsIdx, ts)
e3, c3, depth = run("quick", quicksort, ByTsIdx, ts)
r, passes = radix_sort([(t, i) for i, t in enumerate(ts)])
assert [e.i for e in e1] == [e.i for e in e2] == [e.i for e in e3] == [p[1] for p in r] == ref
print(f" {name:<20}{c1:>10}{c2:>12}{c3:>11}{passes:>15} {depth}")
print(f" n-1 = {N - 1}, n(n-1)/2 = {N * (N - 1) // 2}")
print("\nstability with tagged equal timestamps (input order a b c d e f, timestamps 2 1 2 1 2 1):")
stamps = [2, 1, 2, 1, 2, 1]
for label, sorter, cls in (("list.sort, timestamp only", lambda e: e.sort(), ByTs),
("merge sort, timestamp only", merge_sort, ByTs),
("quicksort, timestamp only", quicksort, ByTs),
("quicksort, timestamp + index", quicksort, ByTsIdx)):
entries, _, _ = run(label, sorter, cls, stamps)
print(f" {label:<30}", " ".join("abcdef"[e.i] + str(e.ts) for e in entries))
r, _ = radix_sort([(t, i) for i, t in enumerate(stamps)])
print(f" {'radix, 8-bit passes':<30}", " ".join("abcdef"[i] + str(t) for t, i in r))
print("\nedge cases: empty / one / all equal")
for stamps in ([], [5], [7] * 4):
e, c, _ = run("", lambda e: e.sort(), ByTsIdx, stamps)
m, _, _ = run("", merge_sort, ByTsIdx, stamps)
q, _, _ = run("", quicksort, ByTsIdx, stamps)
r, p = radix_sort([(t, i) for i, t in enumerate(stamps)])
print(" ", stamps, [x.i for x in e], [x.i for x in m], [x.i for x in q], [x[1] for x in r], "passes", p)
Run with Python 3.12, it prints:
comparisons for n = 2000 (radix: passes of 8 bits, and zero comparisons)
input list.sort merge sort quicksort radix passes quicksort stack
random 19239 19462 23274 5 6
already sorted 1999 10864 1999000 5 1
1% moved 4313 14191 611400 5 3
reversed 1999 11088 1999000 5 1
50 distinct stamps 17695 19348 27448 1 6
n-1 = 1999, n(n-1)/2 = 1999000
stability with tagged equal timestamps (input order a b c d e f, timestamps 2 1 2 1 2 1):
list.sort, timestamp only b1 d1 f1 a2 c2 e2
merge sort, timestamp only b1 d1 f1 a2 c2 e2
quicksort, timestamp only f1 d1 b1 a2 c2 e2
quicksort, timestamp + index b1 d1 f1 a2 c2 e2
radix, 8-bit passes b1 d1 f1 a2 c2 e2
edge cases: empty / one / all equal
[] [] [] [] [] passes 0
[5] [0] [0] [0] [0] passes 0
[7, 7, 7, 7] [0, 1, 2, 3] [0, 1, 2, 3] [0, 1, 2, 3] [0, 1, 2, 3] passes 0
Reading the output
- On random timestamps at n = 2000,
list.sortmade 19239 comparisons, merge sort 19462 and quicksort 23274. - On already sorted or reversed input,
list.sortmade 1999 (that is n-1: it finds one run and stops), merge sort 10864 and 11088, and the shipped quicksort 1,999,000 = n(n-1)/2. That is about 86 times the quicksort's own work on random input (1,999,000 against 23,274), and about 104 times the worklist.sortdid on random input (19,239). The cause is the pivot rule: with the last element as pivot, a sorted range splits into an empty part and a part with one fewer element every time, so n-1 partitions of decreasing size. Choosing the middle element or a random one, or median of three, removes this particular input but not a crafted one; introsort (quicksort that switches to heapsort when recursion gets deep) is what bounds the worst case, and cppreference notes it is usually used to meetstd::sort's O(N log N) requirement, butstd::sortis documented as not preserving the order of equal elements. - Merge sort adapts less than Timsort: its top-down splits do not look for runs, so a sorted input still costs 10,864 comparisons, 44% fewer than its random-input 19,462, while
list.sortfalls from 19,239 to 1,999 (90% fewer). - On the input with 1% of the entries moved,
list.sortneeded 4313 comparisons (about 2.2 n), merge sort 14191 and the shipped quicksort 611400. Logs that arrive mostly in order look like this input. - Radix ran 5 passes of 8 bits on these timestamps (epoch milliseconds are about 41 bits, and the varying part of these timestamps spans five of the eight bytes), 1 pass when only 50 distinct values exist, and no comparisons at all. It does the same 5 passes on sorted input, which is why it has no advantage there.
- The deepest quicksort stack was 6 ranges at n = 2000, as the smaller-side-first rule intends, so stack memory is not the problem; the time is.
- The stability test: with timestamps 2 1 2 1 2 1 on records a to f,
list.sort, merge sort, and radix returnedb1 d1 f1 a2 c2 e2(equal timestamps in input order). Quicksort on the timestamp alone returnedf1 d1 b1 a2 c2 e2, so the ones reversed. Adding the index to the comparison key fixed it, because no two entries then compare equal. - Edge cases: empty, one-element and all-equal input work in every sort, and all-equal input leaves the order untouched.
Memory and copying
For the merge sort, the total copying work and the peak extra memory are different numbers: every level moves all n entries once into the buffer and once back, so O(n log n) entry moves in total, while the buffer is allocated once and holds n entries. The copy-back uses a loop rather than a slice because a slice would create a temporary list of the same size and raise the peak. Timsort's own scratch is smaller, up to n/2 entries.
Recommendation and what would flip it
Commit to Timsort on (timestamp, offset) entries: stable by specification, bounded tail, a fast path for the nearly ordered data that timestamps usually form, and a modest scratch buffer. Change the choice if (a) memory is so tight that even n/2 entries is too much: use introsort on (timestamp, index) entries, which is deterministic and stable-by-construction through the index, and accept that it does not speed up on ordered input; (b) timestamps arrive in random order and n is very large: radix sort does a fixed number of linear passes with no comparisons, at the price of a full n-entry buffer; (c) the library offers only an unstable sort: make the original index part of the key.
Common mistakes
- Sorting the variable-length records themselves, so every swap copies different byte counts.
- Believing quicksort's average case is its tail: the worst case is what sets the tail latency, and it depends on the pivot rule.
- Assuming a library sort is stable without checking its documentation; tagged equal keys are the test.
- Treating radix sort as always faster: on sorted input it still pays every pass.
Given an m x n matrix where each row is sorted left-to-right and each column is sorted top-to-bottom, implement in Python def search_matrix(matrix: List[List[int]], target: int) -> bool that returns True when target exists. Aim for O(m+n) time using the staircase search (start at top-right or bottom-left). Explain why this method is preferred over naive binary search on every row for certain shapes of m and n and include sample inputs and constraints.
Sample Answer
The idea in plain words
Both rows and columns are sorted, so the top-right corner is special: it is the largest value in its row and the smallest value in its column. Compare it with the target:
- value > target: the target cannot be anywhere in this column below it (those values are even larger), so drop the whole column and step left.
- value < target: the target cannot be anywhere in this row to its left (those values are even smaller), so drop the whole row and step down.
- equal: found.
Every comparison removes a full row or a full column, so after at most m + n - 1 comparisons you either find the target or walk off the grid. The bottom-left corner works the same way with the directions swapped. The other two corners do not work: at the top-left both neighbours (right and down) are larger, so a comparison cannot rule out a row or a column.
Sample input and constraints
Rows are sorted left to right in non-decreasing order (each value is at least the one before it, so equal neighbours are allowed), columns are sorted top to bottom in non-decreasing order, values are integers, duplicates are allowed, and m or n may be 0 (then the answer is False). Note this is weaker than "each row starts above the last element of the previous row" (the other classic matrix problem), which allows one plain binary search over the flattened grid.
Brute force, and the competing method
- Scan every cell: O(m * n).
- Binary search each row: O(m log n). Binary search on a sorted row compares the middle cell with the target and throws away the half that cannot hold it, so a row of n cells needs about log2 n comparisons instead of n. It is the natural next step, and it is better than the staircase for some shapes (below).
- Staircase: O(m + n) time, O(1) space.
The code
import random
from typing import List
def search_matrix(matrix: List[List[int]], target: int, steps=None) -> bool:
"""Staircase search. Start at the top-right corner and walk left or down.
steps, if given, is a list that receives one entry per comparison made.
"""
if not matrix or not matrix[0]:
return False
row, col = 0, len(matrix[0]) - 1
while row < len(matrix) and col >= 0:
value = matrix[row][col]
if steps is not None:
steps.append((row, col, value))
if value == target:
return True
if value > target:
col -= 1 # everything below this value in its column is larger too
else:
row += 1 # everything left of this value in its row is smaller too
return False
def search_by_row_bisect(matrix: List[List[int]], target: int, steps=None) -> bool:
"""The alternative: one binary search per row. steps counts comparisons."""
for row in matrix:
lo, hi = 0, len(row)
while lo < hi: # same loop as bisect_left, written out so it can be counted
mid = (lo + hi) // 2
if steps is not None:
steps.append(1)
if row[mid] < target:
lo = mid + 1
else:
hi = mid
if lo < len(row) and row[lo] == target:
return True
return False
grid = [
[1, 4, 7, 11],
[2, 5, 8, 12],
[3, 6, 9, 16],
[10, 13, 14, 17],
]
for target in (9, 15):
path = []
found = search_matrix(grid, target, path)
print(f"target={target} found={found}")
for r, c, v in path:
move = "found" if v == target else ("left" if v > target else "down")
print(f" at ({r},{c}) value={v:2} -> {move}")
print("\nedge cases")
print("empty matrix ", search_matrix([], 1))
print("one empty row ", search_matrix([[]], 1))
print("one cell, hit ", search_matrix([[5]], 5))
print("one cell, miss ", search_matrix([[5]], 6))
print("single row, hit ", search_matrix([[1, 3, 5, 7]], 7))
print("single column, hit ", search_matrix([[1], [3], [5], [7]], 1))
print("duplicates, hit ", search_matrix([[2, 2], [2, 2]], 2))
# check against plain membership on random sorted-row-and-column matrices
random.seed(11)
cases = 0
for _ in range(2000):
m, n = random.randint(0, 5), random.randint(0, 5)
# a[i][j] = base_row[i] + base_col[j] with both bases non-decreasing keeps rows and columns sorted
br = sorted(random.randint(0, 6) for _ in range(m))
bc = sorted(random.randint(0, 6) for _ in range(n))
mat = [[br[i] + bc[j] for j in range(n)] for i in range(m)]
for t in range(-1, 14):
expected = any(t in row for row in mat)
assert search_matrix(mat, t) == expected, (mat, t)
assert search_by_row_bisect(mat, t) == expected, (mat, t)
cases += 1
print(f"\nrandom (matrix, target) pairs checked against `in`: {cases}")
# comparison counts when the target is absent, for different shapes
print("\nshape (m x n) staircase bisect each row m+n-1 m*ceil(log2(n+1))")
for m, n in [(1000, 1000), (100, 10000), (10, 100000), (1, 100000), (100000, 1)]:
# every entry is even, so the odd target below is absent but sits inside the value range
mat = [[2 * (i + j) for j in range(n)] for i in range(m)]
target = m + n - 1 if (m + n - 1) % 2 == 1 else m + n
s1, s2 = [], []
assert search_matrix(mat, target, s1) is False
assert search_by_row_bisect(mat, target, s2) is False
bound = m * (n).bit_length() # bit_length(n) == ceil(log2(n+1))
print(f"{m:7} x {n:<9} {len(s1):9} {len(s2):17} {m + n - 1:7} {bound:9}")
Output:
target=9 found=True
at (0,3) value=11 -> left
at (0,2) value= 7 -> down
at (1,2) value= 8 -> down
at (2,2) value= 9 -> found
target=15 found=False
at (0,3) value=11 -> down
at (1,3) value=12 -> down
at (2,3) value=16 -> left
at (2,2) value= 9 -> down
at (3,2) value=14 -> down
edge cases
empty matrix False
one empty row False
one cell, hit True
one cell, miss False
single row, hit True
single column, hit True
duplicates, hit True
random (matrix, target) pairs checked against `in`: 30000
shape (m x n) staircase bisect each row m+n-1 m*ceil(log2(n+1))
1000 x 1000 1999 9977 1999 10000
100 x 10000 5149 1336 10099 1400
10 x 100000 50014 168 100009 170
1 x 100000 50000 17 100000 17
100000 x 1 50002 100000 100000 100000
Reading the trace
On the 4 x 4 grid with target 9: start at the top-right value 11, which is larger than 9, so go left to 7. 7 is smaller than 9, so go down to 8, then down to 9: found after four comparisons. For target 15 the walk reaches 16 (go left), then 9 (go down), then 14 (go down) and then falls off the bottom edge (row == 4), so the answer is False after five comparisons.
Why prefer the staircase, and when not to
The comparison counts above come from the real functions with the target absent (the worst case for the row-wise search; the staircase reaches its worst case of m + n - 1 only when its walk crosses the whole grid, as it does on the square grid):
- On a square grid, 1000 x 1000, the staircase used 1,999 comparisons, which is exactly m + n - 1. Row-by-row binary search used 9,977, close to its bound m * ceil(log2(n + 1)) = 10,000.
- When one side is much smaller, row-wise binary search wins: 10 rows of 100,000 took 168 comparisons against 50,014 for the staircase (whose bound for that shape is 100,009), and a single row of 100,000 took 17 against 50,000.
- When there are many rows and one column (100,000 x 1), row-wise binary search spent 100,000 comparisons and the staircase 50,002. Both are linear in m there; this is where one should binary search the single column instead.
Where the last column comes from: a binary search over a row of n cells makes at most ceil(log2(n + 1)) comparisons, and in Python n.bit_length() (the number of binary digits of n) equals exactly that value. For n = 1, 3, 7, 8 it gives 1, 2, 3, 4, and for n = 1,000,000 it gives 20. Multiplying by the m rows gives the bound m * n.bit_length().
A hand-worked case with m = 5 rows and n = 1,000,000 columns shows why the shape decides. The staircase can need up to m + n - 1 = 5 + 1,000,000 - 1 = 1,000,004 comparisons. Binary searching each row needs at most 5 * 20 = 100. Here the per-row search is about ten thousand times cheaper. On the 1000 x 1000 grid it is the other way round: m + n - 1 = 1,999 against 1000 * 10 = 10,000.
So the rule is to compare m + n with m * log2(n) (and, symmetrically, n * log2(m), by searching down columns). Close to square the staircase wins; very wide or very tall shapes favour binary search along the short side. The staircase's other advantages are that it needs no sub-search code and that its worst-case count has no logarithm hidden in it.
Complexity
- Time O(m + n) worst case: each loop pass moves
rowdown orcolleft, and there are at most m rows and n columns to cross, so at most m + n - 1 comparisons. The first row of the table confirms the count equals the bound. - Space O(1): two indices; nothing is sliced or copied.
Edge cases and common mistakes
- Empty matrix
[]and a matrix with empty rows[[]]: guarded at the top; both printFalse. - One cell, one row, one column: all handled by the same loop (see the outputs above).
- Duplicates: fine, the comparisons use
>and<against the target and==returns at once. - Starting at the top-left corner: the mistake that cannot be fixed by tuning the loop, because no comparison there rules anything out.
- Wrong loop bounds: the condition needs both
row < len(matrix)andcol >= 0; without thecol >= 0test,colgoes to -1 and Python readsmatrix[row][-1], the last cell of the row again, so the walk keeps stepping over cells it has already ruled out untilcolreaches -(n + 1) and anIndexErroris raised (for examplesearch_matrix([[5]], 4)). - Using
target in rowfor every row: that is O(m * n), no better than a flat scan.
The code was also checked against in membership on 2,000 random matrices with every target from -1 to 13, for both the staircase and the row-bisect version (the printed pair count is the number of checked cases).
Follow-ups
- Count how many cells are less than or equal to a target: the same walk, adding a whole row or column slice per step (the basis of the k-th smallest in a sorted matrix problem).
- Return the position instead of a boolean: return
(row, col)at the==branch. - Matrix stored on disk in blocks: binary search by row first to limit I/O, or walk the staircase block by block.
Running the code
python3 staircase.py # save the code above as staircase.py; tested on Python 3.12
Unlock Full Question Bank
Get access to all Sorting and Searching Algorithms interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.