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.
Explain Introsort (introspective sort): how it combines quicksort, heapsort fallback, and insertion sort for small partitions. Provide pseudocode for introsort and explain why it guarantees O(n log n) worst-case behavior. Describe how std::sort implements these ideas and discuss tuning parameters like recursion-depth threshold.
Sample Answer
The idea in plain words
Introsort ("introspective sort") is quicksort that watches itself. Quicksort is fast on typical data but degrades to O(n^2) when its pivot choices keep splitting the range badly. Introsort sets a depth budget for the quicksort recursion, normally 2 * floor(log2 n). If a range is still unsorted when the budget runs out, the pivots have been bad, so it abandons quicksort on that range and finishes it with heapsort, which is O(n log n) in the worst case (but has larger constants: more fixed work per element, so it is slower than quicksort on typical data). Heapsort arranges the array as a heap, an array read as a tree where element i has children 2i+1 and 2i+2 and every parent is at least as large as its children, so the largest item sits at index 0; it then repeatedly swaps that largest item to the end of the unsorted part and repairs the heap by sinking the new top item (sift_down). Insertion sort takes each element in turn and slides it left past larger elements until it fits, like sorting a hand of cards. Partitioning (used by quicksort) picks a pivot value and rearranges a range so that smaller items come before it and larger items after it; the pivot is then in its final place. Ranges that shrink to a small size are left to insertion sort, which beats the recursive methods on tiny inputs. Each ingredient covers another's weak spot: quicksort is fastest on typical data, heapsort bounds the worst case, insertion sort removes recursion overhead at the bottom.
Pseudocode
introsort(a):
budget = 2 * floor(log2(len(a)))
loop(0, len(a) - 1, budget)
insertion_sort(a) # one pass over the whole array
loop(lo, hi, budget):
while hi - lo + 1 > 16: # small ranges are left for insertion sort
if budget == 0:
heapsort(a[lo..hi]); return # fallback: pivots have been bad
budget -= 1
p = partition(a, lo, hi) # pivot chosen by the pivot rule
loop(p + 1, hi, budget) # recurse on the upper part
hi = p - 1 # loop on the lower part
The three ingredients on tiny inputs
Three short runs show the pieces before the full program. First, a Lomuto partition (sweep left to right, move items smaller than the last-element pivot to the front, finally put the pivot between the small and large groups). Second, heapsort on four items: after building the heap, each line moves the current top to its final index and repairs the heap. Third, the closing insertion pass on three blocks of three items; each block holds values that belong between its neighbours' values but is internally out of order, which is the state quicksort leaves when it stops at small ranges.
def lomuto(a, lo, hi):
"""Partition around a[hi]; return the pivot's final index."""
pivot, store = a[hi], lo
for i in range(lo, hi):
if a[i] < pivot:
a[i], a[store] = a[store], a[i]
store += 1
print(f" i={i} a={a} store={store}")
a[store], a[hi] = a[hi], a[store]
return store
a = [8, 2, 9, 4, 7, 5]
print("partition", a, "pivot", a[-1])
p = lomuto(a, 0, len(a) - 1)
print(f"after: {a}, pivot 5 sits at index {p}; left side is smaller, right side is larger")
def heapsort(a):
n = len(a)
def sift_down(root, end):
while 2 * root + 1 < end:
child = 2 * root + 1
if child + 1 < end and a[child] < a[child + 1]:
child += 1
if a[root] >= a[child]:
return
a[root], a[child] = a[child], a[root]
root = child
for start in range(n // 2 - 1, -1, -1):
sift_down(start, n)
print("heap built (largest on top):", a)
for end in range(n - 1, 0, -1):
a[0], a[end] = a[end], a[0]
sift_down(0, end)
print(f"moved the top to index {end}: {a}")
print()
heapsort([3, 1, 4, 2])
print()
b = [3, 2, 1, 6, 5, 4, 9, 8, 7] # three blocks of 3, each block holds values between its neighbours
moves = []
for i in range(1, len(b)):
x, j = b[i], i - 1
shifts = 0
while j >= 0 and x < b[j]:
b[j + 1] = b[j]
j -= 1
shifts += 1
b[j + 1] = x
moves.append(shifts)
print("final insertion pass result:", b)
print("places each element moved:", moves, "max", max(moves))
Complete output:
partition [8, 2, 9, 4, 7, 5] pivot 5
i=0 a=[8, 2, 9, 4, 7, 5] store=0
i=1 a=[2, 8, 9, 4, 7, 5] store=1
i=2 a=[2, 8, 9, 4, 7, 5] store=1
i=3 a=[2, 4, 9, 8, 7, 5] store=2
i=4 a=[2, 4, 9, 8, 7, 5] store=2
after: [2, 4, 5, 8, 7, 9], pivot 5 sits at index 2; left side is smaller, right side is larger
heap built (largest on top): [4, 2, 3, 1]
moved the top to index 3: [3, 2, 1, 4]
moved the top to index 2: [2, 1, 3, 4]
moved the top to index 1: [1, 2, 3, 4]
final insertion pass result: [1, 2, 3, 4, 5, 6, 7, 8, 9]
places each element moved: [1, 2, 0, 1, 2, 0, 1, 2] max 2
Reading it: in the partition, store marks where the next small item goes, and the pivot 5 ends at index 2 with {2, 4} before it and {7, 8, 9} after it (the two sides are not yet sorted internally, which is the next recursion's job). In the heapsort, [4, 2, 3, 1] is a valid heap (4 is at least 2 and 3, and 2 is at least 1); each later line fixes one more item at the right end. In the last run no element moves more than 2 places, which is block size minus 1: an item can only move within its own block, because everything in earlier blocks is smaller and everything in later blocks is larger.
Runnable version with counts
The code below implements exactly that. It uses a Lomuto partition and supports two pivot rules: the last element, and the median of three (the median of the first, middle and last elements). It compares against a plain quicksort that uses the same partition and pivot rule but has no budget. Every key comparison goes through one counting function, so the tables report comparisons, not time. The worst case of plain quicksort under either pivot rule is O(n^2): sorted input for the last-element rule, and equal keys for both rules, as the first table shows.
import random
THRESHOLD = 16 # ranges this small are left for the final insertion-sort pass
comparisons = 0
def less(x, y):
global comparisons
comparisons += 1
return x < y
# ---------- pivot rules ----------
def pivot_last(a, lo, hi):
return hi
def pivot_median3(a, lo, hi):
"""Index of the median of a[lo], a[mid], a[hi]."""
mid = (lo + hi) // 2
if less(a[lo], a[mid]):
if less(a[mid], a[hi]):
return mid
return hi if less(a[lo], a[hi]) else lo
if less(a[lo], a[hi]):
return lo
return hi if less(a[mid], a[hi]) else mid
def partition(a, lo, hi, rule):
"""Lomuto partition around the chosen pivot; returns the pivot's final index."""
p = rule(a, lo, hi)
a[p], a[hi] = a[hi], a[p]
pivot, store = a[hi], lo
for i in range(lo, hi):
if less(a[i], pivot):
a[i], a[store] = a[store], a[i]
store += 1
a[store], a[hi] = a[hi], a[store]
return store
# ---------- the three ingredients ----------
def insertion_sort(a, lo, hi):
for i in range(lo + 1, hi + 1):
x, j = a[i], i - 1
while j >= lo and less(x, a[j]):
a[j + 1] = a[j]
j -= 1
a[j + 1] = x
def heapsort(a, lo, hi):
n = hi - lo + 1
def sift_down(root, end):
while 2 * root + 1 < end:
child = 2 * root + 1
if child + 1 < end and less(a[lo + child], a[lo + child + 1]):
child += 1
if not less(a[lo + root], a[lo + child]):
return
a[lo + root], a[lo + child] = a[lo + child], a[lo + root]
root = child
for start in range(n // 2 - 1, -1, -1):
sift_down(start, n)
for end in range(n - 1, 0, -1):
a[lo], a[lo + end] = a[lo + end], a[lo]
sift_down(0, end)
def introsort(a, rule, limit=None, stats=None):
"""Quicksort with a depth budget; heapsort when it runs out; insertion sort to finish."""
global comparisons
n = len(a)
if limit is None:
limit = 2 * (n.bit_length() - 1) if n else 0 # 2 * floor(log2 n)
stats = stats if stats is not None else {}
stats.update(fallbacks=0, depth=0)
def loop(lo, hi, budget, depth):
stats["depth"] = max(stats["depth"], depth)
while hi - lo + 1 > THRESHOLD:
if budget == 0:
stats["fallbacks"] += 1
heapsort(a, lo, hi)
return
budget -= 1
p = partition(a, lo, hi, rule)
loop(p + 1, hi, budget, depth + 1) # recurse on the upper part, loop on the lower
hi = p - 1
loop(0, n - 1, limit, 1)
before = comparisons
insertion_sort(a, 0, n - 1) # every element is within THRESHOLD - 1 places of its final spot
stats["insertion_comparisons"] = comparisons - before
return a
def plain_quicksort(a, rule):
"""Same partition and pivot rule, no depth budget, no heapsort, no insertion sort."""
def go(lo, hi):
while lo < hi:
p = partition(a, lo, hi, rule)
if p - lo < hi - p:
go(lo, p - 1)
lo = p + 1
else:
go(p + 1, hi)
hi = p - 1
go(0, len(a) - 1)
return a
def run(sorter, data, *args, **kw):
global comparisons
a = list(data)
comparisons = 0
sorter(a, *args, **kw)
assert a == sorted(data)
return comparisons
# ---------- checks ----------
rng = random.Random(9)
for _ in range(400):
data = [rng.randint(0, 6) for _ in range(rng.randint(0, 80))]
for rule in (pivot_last, pivot_median3):
for limit in (None, 0, 1, 3):
a = list(data)
introsort(a, rule, limit)
assert a == sorted(data)
print("introsort matches sorted() on 400 seeded random arrays, both pivot rules, four depth limits")
n = 1024
inputs = {
"sorted": list(range(n)),
"reverse": list(range(n, 0, -1)),
"all equal": [5] * n,
"random": random.Random(1).sample(range(n), n),
}
print(f"\nn = {n}, depth limit = 2*floor(log2 n) = {2 * (n.bit_length() - 1)}")
print(f"{'pivot rule':<16}{'input':<11}{'plain QS':>10}{'introsort':>11}{'heapsort calls':>16}{'max depth':>11}")
for rule in (pivot_last, pivot_median3):
for name, data in inputs.items():
plain = run(plain_quicksort, data, rule)
st = {}
intro = run(introsort, data, rule, stats=st)
print(f"{rule.__name__:<16}{name:<11}{plain:>10}{intro:>11}{st['fallbacks']:>16}{st['depth']:>11}")
print("\nTuning the depth limit (n = 1024)")
print(f"{'limit':>6} {'last-pivot, sorted':^24} {'median-of-3, random':^24}")
print(f"{'':>6} {'comparisons':>12}{'heapsorts':>11} {'comparisons':>12}{'heapsorts':>11}")
for limit in (0, 2, 5, 10, 20, 40, 80):
s1, s2 = {}, {}
c1 = run(introsort, inputs["sorted"], pivot_last, limit=limit, stats=s1)
c2 = run(introsort, inputs["random"], pivot_median3, limit=limit, stats=s2)
print(f"{limit:>6} {c1:>12}{s1['fallbacks']:>11} {c2:>12}{s2['fallbacks']:>11}")
Complete output:
introsort matches sorted() on 400 seeded random arrays, both pivot rules, four depth limits
n = 1024, depth limit = 2*floor(log2 n) = 20
pivot rule input plain QS introsort heapsort calls max depth
pivot_last sorted 523776 38958 1 2
pivot_last reverse 523776 37360 1 12
pivot_last all equal 523776 24299 1 21
pivot_last random 10993 11952 0 10
pivot_median3 sorted 9228 7173 0 7
pivot_median3 reverse 16257 17515 0 7
pivot_median3 all equal 526845 24359 1 21
pivot_median3 random 10933 10950 0 9
Tuning the depth limit (n = 1024)
limit last-pivot, sorted median-of-3, random
comparisons heapsorts comparisons heapsorts
0 19083 1 18339 1
2 21086 1 17364 4
5 24088 1 14461 14
10 29069 1 10950 0
20 38958 1 10950 0
40 58427 1 10950 0
80 96182 1 10950 0
Reading the output
- The guarantee in action. With the last element as pivot, plain quicksort needs 523,776 comparisons on 1024 sorted keys (that is n(n-1)/2), and introsort needs 38,958 with one heapsort call. With the median-of-three rule, sorted input is easy (9,228 versus 7,173), but 1024 equal keys again cost 526,845 for plain quicksort, because Lomuto sends keys equal to the pivot to one side. Introsort finishes the all-equal input in 24,359 comparisons with one heapsort call.
- Cost when nothing goes wrong. On random input the budget is never exhausted (0 heapsort calls), and the introsort count (11,952 and 10,950) is slightly above plain quicksort (10,993 and 10,933); the difference is the work below 16 elements, where insertion sort replaces quicksort. The budget costs nothing in recursion work: it is one integer.
- Depth. The "max depth" column never exceeds 21 (the limit of 20 plus the outermost call), so the stack is O(log n).
- Tuning the budget. With the default of 20 and the last-pivot sorted input, 20 useless partition passes (about n comparisons each) happen before the fallback: 38,958 comparisons. Budget 0 goes straight to heapsort: 19,083. For random input with median-of-three, a budget of 10 or more never falls back (10,950), while a budget of 5 triggers 14 heapsort calls (14,461) and a budget of 0 sorts everything with heapsort (18,339). Read the table by comparing the default row (20) with the row for 0 in each column. So a smaller budget bounds the damage faster on bad inputs but triggers the slow path on healthy ones, and
2 * floor(log2 n)is a compromise.
Why the worst case is O(n log n)
- Quicksort phase. A level is one generation of recursive calls: the first partition is level 1, the partitions of its two parts are level 2, and so on. Along any path of the recursion, at most
budgetpartitions happen. Partitions at the same level work on disjoint ranges, so one level costs at most n comparisons in total, and the phase costs at mostn * 2 * floor(log2 n)plus a few comparisons per partition for the median of three: O(n log n). - Heapsort phase. Each fallback sorts a range of size s in O(s log s) comparisons, the ranges are disjoint, so all fallbacks together cost O(n log n).
- Insertion phase. Every range left unsorted has at most 16 elements, and partitioning has already put every element between the correct neighbours at the range boundaries (the picture is the three-block run above, with blocks of 16 instead of 3). An element can therefore only move inside its own range, fewer than 16 places: O(16 n) = O(n).
The sum is O(n log n) for every input. Extra space is the recursion depth, at most budget + 1 frames, plus O(1) for heapsort and insertion sort, so O(log n).
How std::sort does it
In an interview the expected answer is the three-part structure above: a depth budget, a heapsort fallback and an insertion-sort finish. The identifiers named below (__lg, _S_threshold, __move_median_to_first, __partial_sort, __final_insertion_sort) are internal names in one library's source and only matter to someone reading that header. The C++ standard requires O(N log N) comparisons for std::sort (the corrected wording from LWG 713, which cppreference documents), and introsort is the usual way to meet it; the order of equivalent elements is not guaranteed (use std::stable_sort for that). In libstdc++ (GCC 14.2, read from the installed bits/stl_algo.h): the budget is std::__lg(n) * 2, where __lg is floor(log2); the small-range threshold is 16 (_S_threshold); the pivot is the median of three (the second element, the middle and the last; chosen by __move_median_to_first); the fallback is std::__partial_sort(first, last, last), a heap-based sort; and after the introsort loop, one __final_insertion_sort pass finishes the whole range, which is the pass the code above copies. It also recurses on the upper part and loops on the lower, as the code does. Other standard libraries use different constants and details; the standard fixes only the complexity bound.
Tuning parameters
- Budget multiplier (
2in2 * floor(log2 n)): lower falls back sooner, higher gives quicksort more chances. The table shows both directions. - Insertion threshold (16): ranges up to this size skip recursion. Larger values trade more O(k^2) insertion work per range for fewer partition calls; the best value depends on element size and comparison cost.
- Pivot rule: median of three removes the sorted and reverse-sorted cases, yet equal keys still defeat the Lomuto partition above, so the heapsort fallback is what bounds that case.
- Partition scheme: a partition that handles equal keys well (Hoare or three-way) avoids tripping the fallback on duplicate-heavy data.
Edge cases and common mistakes
- Empty, one-element and tiny arrays never reach the loop; the checks above cover random arrays of length 0 to 80 with duplicates, both pivot rules and budgets of 0, 1, 3 and the default.
- Forgetting to decrement the budget inside the
whileloop (only decrementing on recursive calls). The lower-part loop then never sees the budget shrink, so on sorted input with the last-element rule the fallback is never reached and the sort goes back to the quadratic cost of plain quicksort (the next section runs it: 524,679 comparisons against 38,958). - Treating
std::sortas stable: its documentation does not preserve the order of equivalent elements.
The budget mistake, run
This program saves the earlier introsort listing as introsort.py and imports it. It rebuilds the loop with the one-line mistake (the budget shrinks only when recursing) and counts comparisons on sorted input.
import contextlib
import io
import random
with contextlib.redirect_stdout(io.StringIO()): # hide what introsort.py prints when imported
import introsort as I
def budget_only_on_recursion(a, rule):
"""Mistake: the budget shrinks only when recursing, never inside the while loop."""
def loop(lo, hi, budget):
while hi - lo + 1 > I.THRESHOLD:
if budget == 0:
I.heapsort(a, lo, hi)
return
p = I.partition(a, lo, hi, rule)
loop(p + 1, hi, budget - 1)
hi = p - 1
loop(0, len(a) - 1, 2 * (len(a).bit_length() - 1))
I.insertion_sort(a, 0, len(a) - 1)
n = 1024
data = list(range(n))
print(f"sorted, n = {n}, last-element pivot, comparisons:")
print(" answer's introsort: ", I.run(I.introsort, data, I.pivot_last))
print(" budget shrinks only on recursion:", I.run(budget_only_on_recursion, data, I.pivot_last))
print(" plain quicksort, no budget: ", I.run(I.plain_quicksort, data, I.pivot_last))
Run in a python:3.12 container, it prints:
sorted, n = 1024, last-element pivot, comparisons:
answer's introsort: 38958
budget shrinks only on recursion: 524679
plain quicksort, no budget: 523776
Running the code
python3 introsort.py # Python 3.12, standard library only; the runnable listing with counts
python3 ingredients.py # the first listing, the three ingredients on tiny inputs
python3 mistakes.py # the budget mistake; needs introsort.py in the same folder
You are given a comparator supplied by a user that may be inconsistent (non-transitive or throwing exceptions). How would you design a robust sort routine to detect comparator issues, ensure determinism where possible, and fail gracefully? Discuss production safeguards and corrective strategies.
Sample Answer
Direct answer
A comparator is the function a caller supplies to say how two items are ordered: cmp(a, b) returns a negative number when a should come first, zero when they tie, and a positive number when a should come after b. A sort is only meaningful if the comparator describes a real ordering. Three rules define one: comparing an item with itself says "equal" (reflexivity); if a comes before b then b does not come before a (antisymmetry); and if a is not after b and b is not after c, then a is not after c (transitivity). Heights show all three working: Ann 150 cm, Bob 160 cm, Cy 170 cm, and Ann is not after Bob, Bob is not after Cy, so Ann is not after Cy. Rock-paper-scissors breaks transitivity: if "beats" means "comes after", rock comes after scissors, scissors come after paper, and paper comes after rock, a circle in which nothing is smallest. A user-supplied comparator can break any of them, or throw, or return something that is not a number. The robust design has five layers (the Approach section writes them as six steps, with layer 5 split into steps 5 and 6): (1) prefer to turn the comparator into a key that is computed once per item, which removes the whole problem; (2) wrap every call so exceptions and bad return values become one typed error (a dedicated exception class, here ComparatorError, instead of whatever the comparator happened to raise) that names the items involved; (3) test the contract on a sample before sorting; (4) make the order total and deterministic by breaking ties on the original position, and cap the number of comparator calls; (5) verify the result afterwards and fail with a clear error instead of returning an order nobody can trust. None of these checks can prove a comparator is consistent on every pair, so the last line of defence is how the caller handles the error.
What goes wrong with an inconsistent comparator
Python's sorted with functools.cmp_to_key (a helper that wraps a three-way comparator so sorted can use it as a key) does not crash on a bad comparator; it returns some order. The run below uses rock-paper-scissors, where rock beats scissors, scissors beats paper, paper beats rock, so no consistent ordering exists. The six input orders of the three words give three different "sorted" results, so the output depends on the order of the input, not only on its content. That is what breaks determinism in production: the same set of records sorts differently depending on arrival order.
For C++, cppreference documents that std::sort's comparator must satisfy the Compare named requirement, which says the comparator establishes a strict weak ordering (items may tie, but ties behave consistently: comp(a, a) is false; comp(a, b) true implies comp(b, a) false; and transitivity; here comp(a, b) is true when a must come before b, which is a different convention from the three-way numbers above). A comparator that breaks the rules is not just a source of a wrong order in C++. It violates a precondition of std::sort, so the behaviour is undefined: the language standard promises nothing, and a crash is only one of the possible outcomes. The C++ program below gives std::sort a comparator that always answers "true" over 2,000 integers. Built with the command below, one run with g++ 14.2 (libstdc++, Debian, aarch64 container) and AddressSanitizer reported a heap-buffer-overflow READ of size 4 inside std::__unguarded_partition, meaning the sort read past the end of the array. That is one compiler, library version and platform, not a promise about all of them; another version or optimisation level may return an unsorted array or loop instead. It is enough to show why a C++ routine must validate the comparator before sorting: the sort may already have read outside the array before any check of the result could run.
#include <algorithm>
#include <vector>
int main() {
std::vector<int> v(2000);
for (size_t i = 0; i < v.size(); i++) v[i] = (int)((i * 7919) % 1000);
std::sort(v.begin(), v.end(), [](int a, int b) { return true; }); // "a is before b" for every pair
}
Build and run it with g++ -O0 -fsanitize=address always_true.cpp -o always_true && ./always_true; the report above came from GCC 14.2 on Debian (aarch64). A comparator that exceeds a time or call budget, or throws, is a separate failure: the exception escapes from the middle of the sort.
Approach
- Prefer a key. If each item can be mapped once to a value that Python (or the language) already orders consistently, sort with
key=and the user comparator is never called. A key function is called once per item, so a throwing or slow key fails at most n times, early, and a built-in ordering on tuples of numbers and strings is always consistent. Use a comparator only when the order truly cannot be expressed as a key. - Wrap and normalise. Every call goes through one function that counts calls, turns any exception into
ComparatorErrornaming the item positions, rejects booleans, strings and NaN (floating-point "not a number", which is unequal to everything, itself included), and reduces the result to -1, 0 or 1. The reduction(r > 0) - (r < 0)works becauseTruecounts as 1 andFalseas 0: for r = 7 it is 1 - 0, for r = 0 it is 0 - 0, for r = -3 it is 0 - 1. - Check the contract on a sample. Pick up to 8 evenly spaced items, compare every ordered pair (m^2 = 64 calls for m = 8), then check reflexivity, antisymmetry and every triple for transitivity from the stored results.
- Make the order total. Sort the indices, and when the comparator says 0 fall back to comparing positions. In Python
x or ygivesxunlessxis 0, socall(i, j) or (i > j) - (i < j)uses the comparator's answer when it is non-zero and the position order only on a tie. Every pair of distinct items is then strictly ordered, so equal items cannot swap places and the result depends only on the data and the comparator. Python's built-in sort is already stable, so in the runs below the fallback changes no output; it earns its place in languages whose sort is not stable (C++std::sort) and when the same routine is ported there. Cap total calls at4 n ceil(log2 n) + 64unless the caller passes a budget; the sort of a consistent comparator needs about n log2 n at most, so a runaway comparator is cut off. - Verify the result. Compare each neighbouring pair of the output (n-1 calls) and fail if any pair is out of order.
- Fail gracefully. The function returns the sorted list together with a report (calls made, sample calls, budget), or raises
ComparatorError. It never returns a half-checked order. The caller chooses the fallback: reject the request, sort by a safe key such as the record id, or keep the input order and flag the result as unsorted.
Code
import itertools
import math
import random
from functools import cmp_to_key
class ComparatorError(Exception):
"""The user comparator raised, returned a bad value, or broke an ordering rule."""
def safe_sort(items, cmp, sample_size=8, budget=None):
"""Stable sort of `items` by the 3-way comparator cmp(a, b) -> negative / 0 / positive.
Returns (sorted_list, report). Raises ComparatorError instead of returning a wrong order.
"""
n = len(items)
calls = 0
limit = budget if budget is not None else 4 * n * max(1, math.ceil(math.log2(max(n, 2)))) + 64
def call(i, j):
"""Compare items[i] with items[j]; normalise to -1/0/1 and turn every failure into ComparatorError."""
nonlocal calls
calls += 1
if calls > limit:
raise ComparatorError(f"comparator budget of {limit} calls exceeded")
try:
r = cmp(items[i], items[j])
except Exception as exc: # the comparator threw
raise ComparatorError(f"comparator raised {type(exc).__name__}({exc}) on items {i},{j}") from exc
if isinstance(r, bool) or not isinstance(r, (int, float)) or r != r:
raise ComparatorError(f"comparator returned {r!r} for items {i},{j}; need a number")
return (r > 0) - (r < 0)
# 1. Contract check on an evenly spaced sample: reflexive, antisymmetric, transitive.
step = max(1, n // sample_size)
sample = list(range(0, n, step))[:sample_size]
m = {(i, j): call(i, j) for i in sample for j in sample}
for i in sample:
if m[i, i] != 0:
raise ComparatorError(f"cmp(x, x) is {m[i, i]} for item {i}; must be 0")
for i, j in itertools.combinations(sample, 2):
if m[i, j] != -m[j, i]:
raise ComparatorError(f"cmp({i},{j})={m[i, j]} but cmp({j},{i})={m[j, i]}; must be opposite")
for i, j, k in itertools.permutations(sample, 3):
if m[i, j] <= 0 and m[j, k] <= 0 and m[i, k] > 0:
raise ComparatorError(f"not transitive: {i} <= {j} <= {k} but {i} > {k}")
sample_calls = calls
# 2. Sort indices. Ties fall back to the original position, so the order is total and stable.
def by_index(i, j):
return call(i, j) or (i > j) - (i < j)
order = sorted(range(n), key=cmp_to_key(by_index))
# 3. Post-check: every neighbouring pair of the result must be in order (n - 1 more calls).
for a, b in zip(order, order[1:]):
if call(a, b) > 0:
raise ComparatorError(f"result not ordered at items {a},{b}")
return [items[i] for i in order], {"calls": calls, "sample_calls": sample_calls, "budget": limit}
def attempt(label, items, cmp, **kw):
try:
out, rep = safe_sort(items, cmp, **kw)
print(f"{label}: OK {out if len(out) <= 8 else '[...%d items]' % len(out)} {rep}")
except ComparatorError as e:
print(f"{label}: REJECTED: {e}")
if __name__ == "__main__":
plain = lambda a, b: (a > b) - (a < b)
print("sign of 7, 0, -3:", [(r > 0) - (r < 0) for r in (7, 0, -3)])
print("tie-break for (answer, i, j) = (0, 2, 5), (0, 5, 2), (-1, 5, 2):",
[answer or (i > j) - (i < j) for answer, i, j in ((0, 2, 5), (0, 5, 2), (-1, 5, 2))])
attempt("good, ints", [5, 3, 9, 1, 3], plain)
attempt("good, empty", [], plain)
attempt("good, one item", [4], plain)
attempt("good, all equal", [2, 2, 2], plain)
attempt("good, n=1000", list(range(1000, 0, -1)), plain)
# Tagged equal keys: the order of ties must be the input order.
tagged = [(2, "a"), (1, "b"), (2, "c"), (1, "d")]
out, _ = safe_sort(tagged, lambda x, y: plain(x[0], y[0]))
print("stable ties:", out)
# Rock beats scissors beats paper beats rock: antisymmetric but not transitive.
beats = {("rock", "scissors"), ("scissors", "paper"), ("paper", "rock")}
rps = lambda a, b: 0 if a == b else (1 if (a, b) in beats else -1)
names = ["rock", "paper", "scissors"]
raw = {tuple(sorted(p, key=cmp_to_key(rps))) for p in itertools.permutations(names)}
print("plain sorted() on the 6 input orders gives", len(raw), "different 'sorted' results:")
for r in sorted(raw):
print(" ", r)
attempt("cycle rock/paper/scissors", names, rps)
attempt("raises on None", [3, None, 1], plain)
attempt("returns bool (a <= b)", [3, 1, 2], lambda a, b: a <= b)
attempt("returns string", [3, 1], lambda a, b: "less")
coin = random.Random(1)
attempt("random answers", list(range(10)), lambda a, b: coin.choice([-1, 0, 1]))
attempt("budget too small", list(range(10, 0, -1)), plain, budget=5)
attempt("returns int(a <= b)", [3, 1, 2], lambda a, b: int(a <= b))
attempt("always -1", [3, 1, 2], lambda a, b: -1)
attempt("always 0 (every item ties)", [3, 1, 2], lambda a, b: 0)
attempt("always 'first item is before'", [3, 1, 2], lambda a, b: 0 if a == b else -1)
# Correct for the 64 sample calls and the first 6 sort calls, then the answers flip: only the post-check can see it.
seen = [0]
def drifting(a, b):
seen[0] += 1
r = plain(a, b)
return r if seen[0] <= 70 else -r
attempt("answers flip mid-sort", list(range(20, 0, -1)), drifting)
# A cycle among items 37, 38, 39 of 40, which the 8 evenly spaced sample items (0, 5, ..., 35) never touch.
cyc = {(37, 38), (38, 39), (39, 37)}
hidden = lambda a, b: plain(a, b) if (a, b) not in cyc and (b, a) not in cyc else (-1 if (a, b) in cyc else 1)
attempt("hidden cycle, sample of 8", list(range(40)), hidden)
print(" tail of that result:", safe_sort(list(range(40)), hidden)[0][-5:])
attempt("hidden cycle, sample of 40", list(range(40)), hidden, sample_size=40, budget=5000)
Run with Python 3.12, it prints:
sign of 7, 0, -3: [1, 0, -1]
tie-break for (answer, i, j) = (0, 2, 5), (0, 5, 2), (-1, 5, 2): [-1, 1, -1]
good, ints: OK [1, 3, 3, 5, 9] {'calls': 36, 'sample_calls': 25, 'budget': 124}
good, empty: OK [] {'calls': 0, 'sample_calls': 0, 'budget': 64}
good, one item: OK [4] {'calls': 1, 'sample_calls': 1, 'budget': 68}
good, all equal: OK [2, 2, 2] {'calls': 13, 'sample_calls': 9, 'budget': 88}
good, n=1000: OK [...1000 items] {'calls': 2062, 'sample_calls': 64, 'budget': 40064}
stable ties: [(1, 'b'), (1, 'd'), (2, 'a'), (2, 'c')]
plain sorted() on the 6 input orders gives 3 different 'sorted' results:
('paper', 'scissors', 'rock')
('rock', 'paper', 'scissors')
('scissors', 'rock', 'paper')
cycle rock/paper/scissors: REJECTED: not transitive: 0 <= 1 <= 2 but 0 > 2
raises on None: REJECTED: comparator raised TypeError('>' not supported between instances of 'int' and 'NoneType') on items 0,1
returns bool (a <= b): REJECTED: comparator returned True for items 0,0; need a number
returns string: REJECTED: comparator returned 'less' for items 0,0; need a number
random answers: REJECTED: cmp(x, x) is -1 for item 0; must be 0
budget too small: REJECTED: comparator budget of 5 calls exceeded
returns int(a <= b): REJECTED: cmp(x, x) is 1 for item 0; must be 0
always -1: REJECTED: cmp(x, x) is -1 for item 0; must be 0
always 0 (every item ties): OK [3, 1, 2] {'calls': 13, 'sample_calls': 9, 'budget': 88}
always 'first item is before': REJECTED: cmp(0,1)=-1 but cmp(1,0)=-1; must be opposite
answers flip mid-sort: REJECTED: result not ordered at items 6,5
hidden cycle, sample of 8: OK [...40 items] {'calls': 142, 'sample_calls': 64, 'budget': 1024}
tail of that result: [35, 36, 37, 38, 39]
hidden cycle, sample of 40: REJECTED: not transitive: 37 <= 38 <= 39 but 37 > 39
Reading the output
- The first two lines show the two tricks from the code: the sign of 7, 0 and -3 is 1, 0 and -1, and the tie-break keeps the comparator's answer unless it is 0, in which case the positions decide.
- The five
goodlines pass. Forn = 1000reversed the 2062 calls are 64 for the sample, 999 for the sort itself (Timsort, Python's built-in sort, first scans for stretches that are already ordered or strictly descending; a fully reversed input is one descending run, found with n-1 = 999 comparisons and then simply reversed) and 999 for the post-check, so the safeguards (64 + 999 = 1063 calls) are about half of the total on this input. - Ties come out in input order:
(1, 'b')before(1, 'd'), and(2, 'a')before(2, 'c'). Python's stable sort would give the same result without the position fallback. - The cyclic comparator is rejected by the transitivity check on the sample, with the triple named.
- The throwing comparator (
Nonecompared with an int) becomes aComparatorErrornaming items 0 and 1, with the original exception chained. - A comparator returning a bool, or the string
"less", fails the type check on its first call.int(a <= b)returns 1 for two equal items, which fails the reflexivity check. The random comparator fails the same check becausecmp(x, x)came back as -1. - A budget of 5 is exceeded during the 64-call contract check on the sample, before the sort itself starts.
always -1fails the reflexivity check on its first comparison of an item with itself.always 0is accepted on purpose: it says every item is equal to every other, which is a valid (if useless) ordering, and the position fallback returns the input order[3, 1, 2].always 'first item is before'answers -1 for every pair of different items. It is reflexive and passes every triple, so only the antisymmetry check rejects it. The post-check would not: it only asks whether a neighbouring pair compares as positive, and this comparator never does.answers flip mid-sortgives correct answers for its first 70 calls (the 64 of the contract check on this 20-item input plus the first 6 of the sort) and negated answers afterwards, as a comparator that reads shared or changing state would. The sample sees nothing wrong; the post-check finds a neighbouring pair that the drifting answers left out of order and rejects the result.- The last two lines show the limit of sampling. A cycle among items 37, 38 and 39 of 40 sits outside the 8 sampled items (0, 5, ..., 35), so the default run accepts it, and the post-check cannot see it either, because 37 <= 38 and 38 <= 39 hold for the neighbours it compares. Checking all 40 items finds it, but needs an explicit
budget=5000: the 40 x 40 = 1,600 sample calls alone are more than the default budget of 1,024 for 40 items. Full checking costs m^2 calls plus m^3 table lookups, which is only affordable for small inputs.
Complexity, with the reason
For n items and sample size m: the contract check makes m^2 comparator calls and O(m^3) table lookups; the sort makes O(n log n) calls (Timsort's worst case) plus the index tie-break at no extra comparator calls on ties; the post-check makes n-1 calls. Total comparator calls are O(m^2 + n log n), and extra space is O(n) for the index list and O(m^2) for the table.
Production safeguards
- Determinism: the tie-break on position, plus a comparator that reads only its two arguments. A comparator that reads a clock, a random number, a cache or a shared mutable value will answer differently for the same pair at different moments, which is exactly the non-antisymmetric case above. Copy mutable inputs before sorting, so nothing changes mid-sort.
- Expensive or hanging comparators: the call budget bounds the number of calls, but it cannot interrupt one call that never returns. For comparators that call out to another system, run the sort in a worker with a deadline.
- Observability (being able to see from logs and metrics what the system is doing): log the error with the item positions and a count of such failures per comparator, so a bad deployment shows up as a metric.
- Tests: fuzz every comparator you ship (feed it many random inputs) and check the three rules, including equal items and pairs in both argument orders.
- Common mistakes: returning
a <= b(a bool) ora - b(which overflows in fixed-width integer types, shown below; Python ints do not overflow), forgetting the equal case socmp(x, x)is not 0, and sorting a list while another thread changes it.
The a - b mistake is real in Java, where int is 32 bits and wraps around. In an eclipse-temurin:21-jdk container (Java 21, java SubtractComparator.java) this program
import java.util.Arrays;
import java.util.Comparator;
public class SubtractComparator {
public static void main(String[] args) {
Comparator<Integer> bySubtraction = (x, y) -> x - y;
System.out.println("compare(2147483647, -1) = " + bySubtraction.compare(Integer.MAX_VALUE, -1));
Integer[] data = {-1, Integer.MAX_VALUE};
Arrays.sort(data, bySubtraction);
System.out.println("sorted with x - y: " + Arrays.toString(data));
Arrays.sort(data, Integer::compare);
System.out.println("sorted with Integer.compare: " + Arrays.toString(data));
}
}
prints:
compare(2147483647, -1) = -2147483648
sorted with x - y: [2147483647, -1]
sorted with Integer.compare: [-1, 2147483647]
The true difference 2147483647 - (-1) = 2147483648 does not fit in 32 bits, so it wraps to -2147483648 and the comparator claims the larger number comes first. Integer.compare compares the two numbers without subtracting, so it cannot wrap. In C++ the same subtraction is signed overflow, which is undefined behaviour.
Corrective strategies
When a comparator is rejected: fix the comparator (usually a missing tie-break field, which makes it total), switch to a key, or fall back to a conservative ordering such as the record id and tell the caller. Do not retry the same sort hoping for a different answer, since a deterministic comparator will fail the same way and a random one has no right answer.
Explain the behavior and guarantees of C++ STL's nth_element algorithm. What ordering properties does it provide for elements, what is its typical complexity, and when is nth_element preferable to fully sorting the container in practice?
Sample Answer
Direct answer
std::nth_element(first, nth, last) rearranges a range so that the element at position nth is exactly the one that would be there if the whole range were sorted, everything before nth is not greater than it, and everything after is not smaller. Nothing else is promised: the two sides are not sorted, equal elements may land on either side, and the sort is not stable. cppreference states its cost as O(N) comparisons on average (an average-case bound, with the implementation typically introselect). Prefer it to a full sort whenever you need only the k-th smallest, the median, or the k smallest or largest as an unordered set, because it does a fraction of the work.
The idea in plain words
A sort answers "where does every element go?". nth_element answers only "which element belongs at position n, and which elements are on each side of it?". That is a much smaller question, so it can be answered with much less work. Think of finding the median salary in a company: you do not need the full ranking, only a split of "lower half" and "upper half" around the middle person.
Mechanism, in the order it happens: pick a pivot value; partition the range so that smaller values are before it and larger values after; look at where the pivot landed. If it landed exactly on nth, stop. Otherwise discard the side that cannot contain position nth and repeat on the other side only. Because only one side is kept, the work is a series like n + n/2 + n/4 + ..., which adds up to 2n if every pivot splits the range exactly in half. Real pivots split unevenly, so the kept side is usually bigger than half and the total is a few times n (3.66 per element for a plain random-pivot version in the output below, 4.70 for the library), still a constant times n and not n log n. cppreference notes that the implementation is typically introselect: a quickselect that switches to a different method if the partitions stop shrinking fast enough.
Terms: a pivot is the value the range is split around. Quickselect is the pivot-and-keep-one-side loop just described. A comparator is a function that takes two elements and says whether the first must come before the second. operator< is C++'s built-in less-than operator, and std::less{} is the standard object that applies it. v.begin() is an iterator, a marker for the first element, and v.begin() + 4 is the marker for position 4 (counting from 0). libstdc++ is the C++ standard library that ships with g++. A partition step rearranges elements around a pivot; stable means equal elements keep their original relative order; in place means the sort needs only a constant amount of extra memory.
What the function guarantees
cppreference defines the result relative to a hypothetical sorted copy of the range:
[first, nth)is a permutation of the elements that would occupy those positions in the sorted range (so every one of them is not greater than the element atnth). A permutation here means the same elements in any order: for9 4 7 1 8 2 6 3 5 0andnth= 4, the sorted copy is0 1 2 3 4 5 6 7 8 9, so positions 0 to 3 must hold the set {0, 1, 2, 3} in any order, position 4 must hold 4, and positions 5 to 9 must hold {5, 6, 7, 8, 9} in any order.- If
nth != last,*nthis the element that would be at that position in sorted order. [nth + 1, last)is a permutation of the elements that would occupy the remaining positions.
The page states no ordering within either side, and no stability. When nth == last, only the first bullet applies. Introselect is quickselect that falls back to a method with a guaranteed bound if the partitions stop shrinking fast enough. The ordering used is operator< (or std::less{} since C++20), or the comparator you pass.
Code (C++)
nth_properties_hold checks the three bullets above. It first compares v[nth] with the sorted copy. It then copies the left side and the right side into two vectors, rejects any left value above v[nth] or right value below it, sorts both copies, and finally uses std::equal to confirm that the left copy matches the first nth values of the sorted copy and the right copy matches the rest. The last step is what proves each side holds exactly the right values, in any order.
The demo prints a real run, checks the guarantee for every nth on random arrays with many duplicates (against a sorted copy), shows that equal keys do not keep their order, and counts the comparisons for the median of 100,000 values, with the counting done inside the comparator that std::nth_element and std::sort themselves call.
#include <algorithm>
#include <functional>
#include <iostream>
#include <random>
#include <vector>
void show(const char* label, const std::vector<int>& v) {
std::cout << label;
for (int x : v) std::cout << ' ' << x;
std::cout << '\n';
}
// True when v[nth] is the nth smallest, everything before is <= it, everything after is >= it,
// and the two sides hold exactly the values the sorted array holds on each side.
bool nth_properties_hold(const std::vector<int>& v, std::size_t nth, const std::vector<int>& sorted) {
if (v[nth] != sorted[nth]) return false;
std::vector<int> left(v.begin(), v.begin() + nth), right(v.begin() + nth + 1, v.end());
for (int x : left) if (x > v[nth]) return false;
for (int x : right) if (x < v[nth]) return false;
std::sort(left.begin(), left.end());
std::sort(right.begin(), right.end());
return std::equal(left.begin(), left.end(), sorted.begin()) &&
std::equal(right.begin(), right.end(), sorted.begin() + nth + 1);
}
struct Tagged { int key; char tag; };
int main() {
std::vector<int> v = {9, 4, 7, 1, 8, 2, 6, 3, 5, 0};
show("before: ", v);
std::nth_element(v.begin(), v.begin() + 4, v.end());
show("after nth=4: ", v);
std::cout << "v[4] = " << v[4] << ", left side sorted? " << std::is_sorted(v.begin(), v.begin() + 4)
<< ", right side sorted? " << std::is_sorted(v.begin() + 5, v.end()) << "\n\n";
// Property check against a sorted copy, with many duplicates, every nth, sizes 1..30.
std::mt19937 rng(7);
long cases = 0;
for (int trial = 0; trial < 300; ++trial) {
std::size_t n = 1 + rng() % 30;
std::vector<int> base(n);
for (int& x : base) x = static_cast<int>(rng() % 6);
std::vector<int> sorted = base;
std::sort(sorted.begin(), sorted.end());
for (std::size_t nth = 0; nth < n; ++nth) {
std::vector<int> w = base;
std::nth_element(w.begin(), w.begin() + nth, w.end());
if (!nth_properties_hold(w, nth, sorted)) { std::cout << "FAIL\n"; return 1; }
++cases;
}
}
std::cout << cases << " (array, nth) cases satisfy the nth_element guarantee\n";
std::vector<int> empty;
std::nth_element(empty.begin(), empty.begin(), empty.end()); // nth == last on an empty range
std::cout << "empty range with nth == end(): no error\n\n";
// Smallest k and largest k: nth_element then sort only the part you need.
std::vector<int> w = {9, 4, 7, 1, 8, 2, 6, 3, 5, 0};
std::nth_element(w.begin(), w.begin() + 3, w.end());
std::sort(w.begin(), w.begin() + 3);
show("3 smallest, sorted:", std::vector<int>(w.begin(), w.begin() + 3));
w = {9, 4, 7, 1, 8, 2, 6, 3, 5, 0};
std::nth_element(w.begin(), w.begin() + 3, w.end(), std::greater<int>());
std::sort(w.begin(), w.begin() + 3, std::greater<int>());
show("3 largest, sorted: ", std::vector<int>(w.begin(), w.begin() + 3));
// Not stable: tagged equal keys.
std::vector<Tagged> t = {{5, 'a'}, {5, 'b'}, {5, 'c'}, {1, 'd'}, {5, 'e'}, {1, 'f'}, {5, 'g'}, {9, 'h'}};
std::nth_element(t.begin(), t.begin() + 4, t.end(), [](const Tagged& x, const Tagged& y) { return x.key < y.key; });
std::cout << "\ntagged after nth=4:";
for (auto& x : t) std::cout << ' ' << x.key << x.tag;
std::cout << " (input order of the fives: a b c e g)\n";
// Comparison counts for the median of 100000 distinct values.
const std::size_t N = 100000;
std::vector<int> big(N);
for (std::size_t i = 0; i < N; ++i) big[i] = static_cast<int>(i);
std::shuffle(big.begin(), big.end(), rng);
long c_nth = 0, c_sort = 0;
std::vector<int> a = big, b = big;
std::nth_element(a.begin(), a.begin() + N / 2, a.end(), [&](int x, int y) { ++c_nth; return x < y; });
std::sort(b.begin(), b.end(), [&](int x, int y) { ++c_sort; return x < y; });
std::cout << "\nmedian of " << N << " values: nth_element " << c_nth << " comparisons (" << double(c_nth) / N
<< " per element), std::sort " << c_sort << " (" << double(c_sort) / N << " per element)\n";
// The plain loop described above (random pivot, keep one side), one comparison per element per round,
// averaged over 20 seeded runs. Perfect halving every round would cost N + N/2 + N/4 + ... = 2N.
double total = 0;
for (unsigned seed = 1; seed <= 20; ++seed) {
std::mt19937 prng(seed);
std::vector<int> cur = big;
std::size_t k = N / 2;
long c_plain = 0;
while (true) {
int pivot = cur[prng() % cur.size()];
std::vector<int> below, above;
for (int x : cur) {
if (x == pivot) continue;
++c_plain;
(x < pivot ? below : above).push_back(x);
}
if (k == below.size()) break; // the pivot sits exactly at position k
if (k < below.size()) { cur = below; }
else { k -= below.size() + 1; cur = above; }
}
total += c_plain;
}
std::cout << "plain random-pivot selection, average of 20 runs: " << total / 20 / N << " comparisons per element"
<< " (perfect halving: " << 2.0 << ")\n";
return 0;
}
Compiled with g++ 14.2 (g++ -std=c++17 -O2 -Wall, libstdc++), it prints:
before: 9 4 7 1 8 2 6 3 5 0
after nth=4: 2 0 1 3 4 5 6 7 9 8
v[4] = 4, left side sorted? 0, right side sorted? 0
4441 (array, nth) cases satisfy the nth_element guarantee
empty range with nth == end(): no error
3 smallest, sorted: 0 1 2
3 largest, sorted: 9 8 7
tagged after nth=4: 5b 5g 1f 1d 5c 5a 5e 9h (input order of the fives: a b c e g)
median of 100000 values: nth_element 469650 comparisons (4.6965 per element), std::sort 2139857 (21.3986 per element)
plain random-pivot selection, average of 20 runs: 3.6646 comparisons per element (perfect halving: 2)
Reading the output
- After
nth_element(v.begin(), v.begin() + 4, v.end())on9 4 7 1 8 2 6 3 5 0the array is2 0 1 3 4 5 6 7 9 8. Position 4 holds 4, which is the fifth smallest (positions count from 0). Everything before it (2 0 1 3) is smaller, everything after (5 6 7 9 8) is larger, and neither side is sorted (bothis_sortedchecks print 0). - All 4441 (array, nth) cases from 300 random arrays of size 1 to 30 over only six distinct values satisfied the guarantee, including
nthat the first and last position. An empty range withnth == end()is accepted. - The three smallest and three largest come out right after sorting only the first three positions:
0 1 2and9 8 7(for largest, passstd::greater<int>()to both calls). - Not stable: the fives, input order
a b c e g, came out in the orderb g c a ein the tagged test, so equal keys were reordered, andnth_elementmakes no promise either way. - The plain random-pivot loop (average of 20 seeded runs) used 3.66 comparisons per element against the ideal 2 for perfect halving.
- Cost for the median of 100,000 distinct values: 469,650 comparisons (4.70 per element) for
nth_elementagainst 2,139,857 (21.40 per element) forstd::sort, about 4.6 times fewer. These counts are specific to this libstdc++ version and this input; the library's documented guarantee is O(N) on average.
Complexity, with the reason
Typical complexity is O(N) comparisons on average, N being the range length (cppreference's wording; the page gives the average-case bound, not a worst-case one, so do not assume linear in the worst case without checking your library). It rearranges in place with O(1) extra space (an amount that does not grow with N) apart from the recursion or loop state. Compare with a full sort at O(N log N). With a pivot that halves the range each round, the total is a geometric series: N + N/2 + N/4 + ... = 2N, which is 2 per element. Pivots that split unevenly make the constant larger without changing the O(N) shape: the plain random-pivot loop measured 3.66 per element and the library 4.70, both above the ideal 2, and both a fixed multiple of N rather than a multiple of N log N (std::sort measured 21.40).
For the k smallest in order: nth_element once (O(N) on average) and then sort the first k: O(N + k log k).
Python equivalent: numpy.partition
numpy.partition(a, kth) gives the same guarantee, with two differences. It returns a partitioned copy and leaves the input unchanged (so it costs O(n) extra memory), and numpy documents that elements smaller than the kth are placed before it and elements equal or greater after it. The numpy docs say the order inside each partition is undefined, the default kind is 'introselect', and the table in the notes lists it as not stable with O(n) worst case. kth may also be a sequence, which puts several positions in their sorted places at once. It needs pip install numpy:
import random
import numpy as np
a = np.array([9, 4, 7, 1, 8, 2, 6, 3, 5, 0])
p = np.partition(a, 4) # returns a partitioned copy; a is unchanged
print("numpy", np.__version__, "| input unchanged:", a.tolist() == [9, 4, 7, 1, 8, 2, 6, 3, 5, 0])
print("kth value p[4] =", p[4], "| sorted[4] =", np.sort(a)[4])
print("left side all <= p[4]:", bool((p[:4] <= p[4]).all()), "| right side all >= p[4]:", bool((p[5:] >= p[4]).all()))
k = 3
print("3 smallest:", np.sort(np.partition(a, k - 1)[:k]).tolist())
print("3 largest: ", np.sort(np.partition(a, len(a) - k)[len(a) - k:])[::-1].tolist())
rng = random.Random(7)
for _ in range(300):
n = rng.randint(1, 30)
data = np.array([rng.randint(0, 5) for _ in range(n)])
s = np.sort(data)
for kth in range(n):
q = np.partition(data, kth)
assert q[kth] == s[kth] and (q[:kth] <= q[kth]).all() and (q[kth + 1:] >= q[kth]).all()
assert sorted(q[:kth].tolist()) == s[:kth].tolist() and sorted(q[kth + 1:].tolist()) == s[kth + 1:].tolist()
print("300 random arrays with duplicates: every kth satisfies the partition guarantee")
Run with Python 3.12, it prints:
numpy 2.5.4 | input unchanged: True
kth value p[4] = 4 | sorted[4] = 4
left side all <= p[4]: True | right side all >= p[4]: True
3 smallest: [0, 1, 2]
3 largest: [9, 8, 7]
300 random arrays with duplicates: every kth satisfies the partition guarantee
For top-k with numpy, partition at n - k and take the tail, then sort only those k if order matters. Without numpy, the standard library offers heapq.nsmallest and heapq.nlargest for small k, or a full sorted.
When nth_element is the right tool, and when it is not
Use it for: a median or percentile; the k-th smallest; the top k of a large array when order among the k does not matter or can be sorted afterwards; pivot selection in a custom sort.
Use something else when: you need the full order (sort); you need stability (stable_sort, or add the original index to the comparison); you need many different ranks from one array (sort once and index, since each nth_element call costs O(N) again and rearranges the array); or the array must not be modified (copy it first, which numpy.partition already does).
Common mistakes
- Assuming the left or right side is sorted.
- Assuming equal elements end up on one particular side: in C++ they may be on both.
- Off-by-one:
nthis a 0-based position, sobegin() + 4is the fifth smallest. - Expecting a stable result.
- Calling it repeatedly in a loop for each k instead of sorting once.
Implement lower_bound and upper_bound on a sorted array: the first index with value >= target and the first index with value > target. Use them to count occurrences, and list the off-by-one pitfalls you checked.
Sample Answer
Direct answer
lower_bound(arr, x) returns the first index whose value is greater than or equal to x; upper_bound(arr, x) returns the first index whose value is strictly greater than x. Both return len(arr) when no such index exists. They are the same loop with one character of difference (< becomes <=): the lower bound moves right while arr[mid] < x, the upper bound while arr[mid] <= x. The number of occurrences of x is upper_bound - lower_bound, in O(log n) time.
The idea in plain words
In a sorted array, think of the values as three runs for a given x: first the values smaller than x, then the values equal to x, then the values bigger than x. lower_bound finds where the equal run begins, upper_bound finds where it ends (one past its last element). The distance between them is the run's length, which is the count. If x is absent, both functions return the same index (the position where x would be inserted to keep the array sorted), and the count is 0.
Brute force
arr.count(x) or a loop scans the whole array: O(n). Binary search finds the two boundaries with about log2(n) steps each: for 1,000,000 items that is at most 20 halvings, against up to 1,000,000 reads for the scan.
Approach and invariant
Use a half-open window [lo, hi): the square bracket means lo is inside the window and the round bracket means hi is outside it, so [0, 6) over six items covers indices 0, 1, 2, 3, 4, 5. Start with lo = 0 and hi = len(arr) (one past the end, so the answer len(arr) is reachable). Invariant, in words: every index left of lo holds a value on the "go right" side (smaller than x for the lower bound, smaller or equal for the upper bound), and every index from hi on holds a value on the other side. The undecided positions are the ones between lo and hi.
- If
arr[mid]is on the left side, thenmidand everything before it are decided:lo = mid + 1. - Otherwise
midmay be the boundary itself, so it stays in the window:hi = mid.
The loop ends when lo == hi, and that index is the boundary.
Code
Each function has its own loop so each invariant stays visible. The driver prints lo, hi and mid for target 2 in [1, 2, 2, 2, 5, 7], then edge cases (target below, between, at the ends and above everything; an empty array; an all-equal array), a buggy version to show an off-by-one pitfall, and a check of 5000 random cases (seed 3) against the standard library's bisect_left, bisect_right and list.count.
import random
from bisect import bisect_left, bisect_right
from typing import List
def lower_bound(arr: List[int], target: int, trace: bool = False) -> int:
"""First index i with arr[i] >= target (len(arr) if there is none).
Invariant: arr[j] < target for every j < lo, and arr[j] >= target for every j >= hi.
"""
lo, hi = 0, len(arr) # hi is one past the last candidate
while lo < hi:
mid = lo + (hi - lo) // 2
if trace:
print(f" lower: lo={lo} hi={hi} mid={mid} arr[mid]={arr[mid]}")
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
def upper_bound(arr: List[int], target: int, trace: bool = False) -> int:
"""First index i with arr[i] > target (len(arr) if there is none).
Invariant: arr[j] <= target for every j < lo, and arr[j] > target for every j >= hi.
"""
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if trace:
print(f" upper: lo={lo} hi={hi} mid={mid} arr[mid]={arr[mid]}")
if arr[mid] <= target: # the only change from lower_bound: < becomes <=
lo = mid + 1
else:
hi = mid
return lo
def count_occurrences(arr: List[int], target: int) -> int:
return upper_bound(arr, target) - lower_bound(arr, target)
def buggy_lower_bound(arr: List[int], target: int) -> int:
"""Pitfall: hi = len(arr) - 1 can never return len(arr)."""
lo, hi = 0, len(arr) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
if __name__ == "__main__":
arr = [1, 2, 2, 2, 5, 7]
print("arr =", arr)
print("target 2")
print(" lower_bound ->", lower_bound(arr, 2, trace=True))
print(" upper_bound ->", upper_bound(arr, 2, trace=True))
print(" count ->", count_occurrences(arr, 2))
for t in (0, 1, 3, 7, 8):
print(f"target {t}: lower={lower_bound(arr, t)} upper={upper_bound(arr, t)} count={count_occurrences(arr, t)}")
print("empty array:", lower_bound([], 4), upper_bound([], 4), count_occurrences([], 4))
print("all equal [6,6,6] target 6:", lower_bound([6, 6, 6], 6), upper_bound([6, 6, 6], 6))
print("\npitfall: hi = len(arr) - 1")
print(" buggy_lower_bound(arr, 8) =", buggy_lower_bound(arr, 8), " correct:", lower_bound(arr, 8))
rng = random.Random(3)
for _ in range(5000):
a = sorted(rng.randint(0, 6) for _ in range(rng.randint(0, 10)))
t = rng.randint(-1, 7)
assert lower_bound(a, t) == bisect_left(a, t)
assert upper_bound(a, t) == bisect_right(a, t)
assert count_occurrences(a, t) == a.count(t)
print("5000 random checks against bisect and list.count passed")
Run in a python:3.12 container, it prints:
arr = [1, 2, 2, 2, 5, 7]
target 2
lower: lo=0 hi=6 mid=3 arr[mid]=2
lower: lo=0 hi=3 mid=1 arr[mid]=2
lower: lo=0 hi=1 mid=0 arr[mid]=1
lower_bound -> 1
upper: lo=0 hi=6 mid=3 arr[mid]=2
upper: lo=4 hi=6 mid=5 arr[mid]=7
upper: lo=4 hi=5 mid=4 arr[mid]=5
upper_bound -> 4
count -> 3
target 0: lower=0 upper=0 count=0
target 1: lower=0 upper=1 count=1
target 3: lower=4 upper=4 count=0
target 7: lower=5 upper=6 count=1
target 8: lower=6 upper=6 count=0
empty array: 0 0 0
all equal [6,6,6] target 6: 0 3
pitfall: hi = len(arr) - 1
buggy_lower_bound(arr, 8) = 5 correct: 6
5000 random checks against bisect and list.count passed
Worked trace
For target 2 in [1, 2, 2, 2, 5, 7] (equal run at indices 1 to 3):
- Lower bound: window
[0, 6),mid3 holds 2 (not smaller),hibecomes 3. Window[0, 3),mid1 holds 2,hibecomes 1. Window[0, 1),mid0 holds 1 (smaller),lobecomes 1. Result 1. - Upper bound: window
[0, 6),mid3 holds 2 (not greater),lobecomes 4. Window[4, 6),mid5 holds 7 (greater),hibecomes 5. Window[4, 5),mid4 holds 5,hibecomes 4. Result 4. - Count: 4 - 1 = 3, matching the three 2s.
Complexity
Each function halves a window of size n, so O(log n) time (at most floor(log2 n) + 1 iterations) and O(1) space. Counting occurrences calls both, so it is O(log n) as well, compared with O(n) for a scan. These two functions are the building blocks for "first and last position", "insert position" and "how many values fall in [a, b]", which is upper_bound(b) - lower_bound(a).
Off-by-one pitfalls checked
- Window end. Starting with
hi = len(arr) - 1andwhile lo < hican never returnlen(arr). The run shows the failure: for target 8 in[1, 2, 2, 2, 5, 7]the buggy version returns 5, while the correct answer is 6. - Wrong comparison. Using
<in the upper bound (or<=in the lower bound) swaps the two functions; for target 2 the upper bound would return 1 instead of 4. - Shrinking the window incorrectly.
hi = mid - 1throws away a possible boundary;lo = midinstead ofmid + 1can loop forever once the window is down to one element, wheremidequalslo(shown in the run after this list). - Out-of-range reads. The functions never read
arr[len(arr)], becausemid < hi <= len(arr). Code that readsarr[lo]after the loop must first testlo < len(arr). - Midpoint overflow.
lo + (hi - lo) // 2instead of(lo + hi) // 2for fixed-width integers (a 32-bit signedintoverflows whenlo + hiexceeds 2,147,483,647). - Empty array.
hi = 0so the loop never runs; both functions return 0 and the count is 0. - All-equal array.
[6, 6, 6]with target 6 gives lower 0 and upper 3, count 3, with no special case.
Two claims above are easy to check with a short program: the stuck loop of pitfall 3 and the step count. It uses the same half-open window, and the last line shows what [0, 6) covers.
import math
def stuck_lower_bound(arr, target, max_rounds=4):
"""Pitfall: lo = mid instead of lo = mid + 1."""
lo, hi = 0, len(arr)
for _ in range(max_rounds):
if lo >= hi:
print(" finished")
return lo
mid = lo + (hi - lo) // 2
print(f" lo={lo} hi={hi} mid={mid} arr[mid]={arr[mid]}")
if arr[mid] < target:
lo = mid # bug: should be mid + 1
else:
hi = mid
print(f" still undecided after {max_rounds} rounds: lo={lo} hi={hi}")
return None
def lower_bound_steps(n, target):
arr = list(range(n))
lo, hi, steps = 0, n, 0
while lo < hi:
mid = lo + (hi - lo) // 2
steps += 1
if arr[mid] < target:
lo = mid + 1
else:
hi = mid
return steps
print("target 2 in [1, 3], with lo = mid:")
stuck_lower_bound([1, 3], 2)
n = 1_000_000
print("n =", n, "steps:", lower_bound_steps(n, n), "bound floor(log2 n) + 1 =", math.floor(math.log2(n)) + 1)
print("window [0, 6) covers indices:", list(range(0, 6)))
Run in a python:3.12 container, it prints:
target 2 in [1, 3], with lo = mid:
lo=0 hi=2 mid=1 arr[mid]=3
lo=0 hi=1 mid=0 arr[mid]=1
lo=0 hi=1 mid=0 arr[mid]=1
lo=0 hi=1 mid=0 arr[mid]=1
still undecided after 4 rounds: lo=0 hi=1
n = 1000000 steps: 19 bound floor(log2 n) + 1 = 20
window [0, 6) covers indices: [0, 1, 2, 3, 4, 5]
Read it like this: with lo = mid, the window [0, 1) has mid = lo = 0, arr[0] is smaller than the target, and lo = mid leaves the window unchanged, so every later round is identical. A window of one element is where mid equals lo, which is why the fix is mid + 1. For one million items the loop ran 19 times, and the bound floor(log2 n) + 1 allows 20.
Node.js version
The same logic with JavaScript signatures lowerBound(arr, target), upperBound(arr, target) and countOccurrences(arr, target). The midpoint uses >> 1, a right shift by one bit, which halves a non-negative whole number and drops the remainder (7 >> 1 is 3). It is safe here for arrays shorter than 2^31 elements because JavaScript's bit shifts operate on 32-bit integers. The test calls print the lower bound, upper bound and count for the same data.
function lowerBound(arr, target) {
let lo = 0, hi = arr.length;
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (arr[mid] < target) lo = mid + 1; else hi = mid;
}
return lo;
}
function upperBound(arr, target) {
let lo = 0, hi = arr.length;
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (arr[mid] <= target) lo = mid + 1; else hi = mid;
}
return lo;
}
const countOccurrences = (arr, target) => upperBound(arr, target) - lowerBound(arr, target);
const arr = [1, 2, 2, 2, 5, 7];
console.log(lowerBound(arr, 2), upperBound(arr, 2), countOccurrences(arr, 2));
console.log(lowerBound(arr, 8), upperBound(arr, 0), countOccurrences([], 4));
console.log(lowerBound([6, 6, 6], 6), upperBound([6, 6, 6], 6));
Run in a node:22 container, it prints:
1 4 3
6 0 0
0 3
The three lines are: lower 1, upper 4 and count 3 for target 2; lower 6 for target 8, upper 0 for target 0 and count 0 on an empty array; and lower 0, upper 3 on [6, 6, 6].
Running the code
Python 3.12 (standard library only): python lower_upper_bound.py
Node.js 22: node lower_upper_bound.js
Pitfall check: python window_pitfalls.py
Save the listings as lower_upper_bound.py, lower_upper_bound.js and window_pitfalls.py.
You need the top 100 values out of 10 million numbers. Compare sorting then slicing, quickselect, a size-k heap, and the library's nth_element, and recommend one with complexity and memory reasoning.
Sample Answer
Direct answer
Use a min-heap of size 100: read the 10 million numbers once, keep the 100 largest seen so far in a heap whose root is the smallest of those 100, and replace the root whenever a new number beats it. It uses memory for about 100 numbers instead of 10 million, needs one pass, leaves the data untouched, works when the numbers arrive as a stream or from a file or database cursor (an object that hands out the rows one at a time), and has a worst case that is bounded: O(n log k) comparisons for n values and k = 100. Prefer the library's nth_element (selection inside an already-loaded array) when the 10 million values already sit in one contiguous in-memory array (a single unbroken block of memory, like a C++ vector or a NumPy array) that you are allowed to reorder (it is mutable, meaning the function may rearrange it); prefer sorting and slicing only when you need other order statistics too.
The idea in plain words
Taking the top 100 of 10 million does not need the other 9,999,900 to be in order. Sorting everything is the brute force: O(n log n) comparisons and the whole dataset in memory. The question is how little ordering work answers "which 100 are the largest". Three ideas appear: keep only a running shortlist (the heap), shrink the problem by splitting around a pivot and discarding the side that cannot contain the answer (quickselect, whose library form is nth_element), or sort and slice.
Terms. A min-heap is a tree stored in an array where each parent is no larger than its children, so the smallest item is always at index 0 and replacing it takes O(log size) comparisons. Quickselect partitions the data around a pivot value and recurses into only the part that holds the wanted position. nth_element is the C++ standard-library function that rearranges a range so that the item at position n is the one that would be there in sorted order, with no larger item before it and no smaller item after it. Finding the item for a given sorted position is called an order statistic (the median is one). A guard comparison is the one comparison of each new value with the heap's root that decides whether the value is worth inserting at all. To sift is to move an item down the heap tree, swapping it with its smaller child until each parent is no larger than its children again.
A tiny run shows the heap idea before any large numbers. With k = 3 and the values 5, 1, 9, 3, 7, 8, 2, the first three form the heap, and every later value is compared once with the root (the smallest of the three kept so far): it either beats the root and replaces it, or is discarded. The printed small heap by hand section lists the heap after each value.
The four options, measured by counting comparisons
The Python program counts comparisons between values for sort-then-slice, the size-k heap and quickselect on 200,000 values with k = 100, in three input orders, and prints memory arithmetic for the real size of 10 million doubles. The C++ program counts comparator calls for std::sort and std::nth_element on the same size.
import heapq
import math
import random
import sys
from array import array
class Counted:
calls = 0
def __init__(self, value):
self.value = value
def __lt__(self, other):
Counted.calls += 1
return self.value < other.value
def top_k_sort(values, k):
return [c.value for c in sorted(values)[-k:]]
def top_k_heap(values, k):
"""Min-heap holding the k largest seen so far; heap[0] is the smallest of them."""
heap = list(values[:k])
heapq.heapify(heap)
replacements = 0
for x in values[k:]:
if heap[0] < x: # one comparison per element
heapq.heapreplace(heap, x)
replacements += 1
top_k_heap.replacements = replacements
return [c.value for c in heap]
def heap_breakdown(values, k):
"""Split the heap's comparisons into building the first heap, guard checks and sifting."""
items = [Counted(x) for x in values]
Counted.calls = 0
heap = items[:k]
heapq.heapify(heap)
build = Counted.calls
Counted.calls = 0
replacements = 0
for x in items[k:]:
if heap[0] < x:
heapq.heapreplace(heap, x)
replacements += 1
guards = len(items) - k
sifting = Counted.calls - guards
return build, guards, sifting, replacements
def show_small_heap(values, k):
"""Print the heap after every value, to see accept and reject by hand."""
heap = list(values[:k])
heapq.heapify(heap)
print(f" first {k} values {values[:k]} -> heap {heap} (root first)")
for x in values[k:]:
if heap[0] < x:
dropped = heapq.heapreplace(heap, x)
print(f" {x} beats root {dropped}: {dropped} leaves, heap {heap}")
else:
print(f" {x} does not beat root {heap[0]}: discarded, heap {heap}")
def top_k_quickselect(values, k, rng, first_pivot=False):
"""Random-pivot quickselect finds the threshold; comparisons counted as one per element per round."""
comparisons = 0
items, target = list(values), len(values) - k
while True:
pivot = items[0] if first_pivot else rng.choice(items)
less = [x for x in items if x < pivot]
equal = [x for x in items if x == pivot]
greater = [x for x in items if x > pivot]
comparisons += len(items)
if target < len(less):
items = less
elif target < len(less) + len(equal):
threshold = pivot
break
else:
target -= len(less) + len(equal)
items = greater
above = [x for x in values if x > threshold]
comparisons += len(values) # final filter pass
return sorted(above + [threshold] * (k - len(above))), comparisons
if __name__ == "__main__":
n, k = 200_000, 100
rng = random.Random(8)
shapes = {
"random order": rng.sample(range(10 * n), n),
"ascending": list(range(n)),
"descending": list(range(n, 0, -1)),
}
print(f"n={n:,}, k={k}; comparisons of two values, counted")
print(f"{'input':<13}{'sort+slice':>12}{'heap size k':>13}{'quickselect':>13} heap replacements")
for name, data in shapes.items():
expected = sorted(data)[-k:]
wrapped = [Counted(x) for x in data]
Counted.calls = 0
assert top_k_sort(wrapped, k) == expected
sort_calls = Counted.calls
Counted.calls = 0
assert sorted(top_k_heap(wrapped, k)) == expected
heap_calls = Counted.calls
result, select_calls = top_k_quickselect(data, k, random.Random(1))
assert result == expected
print(f"{name:<13}{sort_calls:>12,}{heap_calls:>13,}{select_calls:>13,} {top_k_heap.replacements:,}")
print(f"random-order replacements predicted by k*ln(n/k) = {k * math.log(n / k):.0f}")
ascending_2000 = list(range(2000))
fixed = top_k_quickselect(ascending_2000, k, rng, first_pivot=True)[1]
randomised = top_k_quickselect(ascending_2000, k, random.Random(1))[1]
print(f"quickselect on 2,000 ascending values: first-element pivot {fixed:,}, random pivot {randomised:,}")
build, guards, sifting, replacements = heap_breakdown(shapes["ascending"], k)
print(f"ascending heap: build {build}, guard checks {guards:,}, sifting {sifting:,}, "
f"total {build + guards + sifting:,}")
print(f" sifting per replacement {sifting / replacements:.2f}; "
f"all comparisons per replacement {(build + guards + sifting) / replacements:.2f}")
print("\nsmall heap by hand, k = 3")
show_small_heap([5, 1, 9, 3, 7, 8, 2], 3)
print("\nmemory arithmetic for n = 10,000,000 doubles")
big = 10_000_000
print(" array('d') of values :", f"{big * array('d').itemsize:,} bytes")
print(" list of float objects :", f"{big * (8 + sys.getsizeof(1.5)):,} bytes (8-byte slot + {sys.getsizeof(1.5)}-byte float object each)")
print(" heap of k=100 (slots only) :", f"{k * 8:,} bytes")
guard = big
print(" heap comparisons, formula :", f"~{guard:,} guard comparisons + ~{round(k * math.log(big / k)):,} replacements")
print(" full sort comparisons, n*log2(n):", f"~{round(big * math.log2(big)):,}")
print("\nedge cases")
few = [Counted(x) for x in (3, 1, 2)]
print(" heap with fewer values than k=5 :", sorted(top_k_heap(few, 5)))
ties = [5, 9, 9, 1, 7, 9, 2]
print(" quickselect, ties at the boundary :", top_k_quickselect(ties, 4, random.Random(0))[0])
print(" heap, ties at the boundary :", sorted(top_k_heap([Counted(x) for x in ties], 4)))
Output (python:3.12):
n=200,000, k=100; comparisons of two values, counted
input sort+slice heap size k quickselect heap replacements
random order 3,257,996 205,908 1,140,763 762
ascending 199,999 1,543,395 583,851 199,900
descending 199,999 200,044 442,620 0
random-order replacements predicted by k*ln(n/k) = 760
quickselect on 2,000 ascending values: first-element pivot 1,998,050, random pivot 7,802
ascending heap: build 192, guard checks 199,900, sifting 1,343,303, total 1,543,395
sifting per replacement 6.72; all comparisons per replacement 7.72
small heap by hand, k = 3
first 3 values [5, 1, 9] -> heap [1, 5, 9] (root first)
3 beats root 1: 1 leaves, heap [3, 5, 9]
7 beats root 3: 3 leaves, heap [5, 7, 9]
8 beats root 5: 5 leaves, heap [7, 8, 9]
2 does not beat root 7: discarded, heap [7, 8, 9]
memory arithmetic for n = 10,000,000 doubles
array('d') of values : 80,000,000 bytes
list of float objects : 320,000,000 bytes (8-byte slot + 24-byte float object each)
heap of k=100 (slots only) : 800 bytes
heap comparisons, formula : ~10,000,000 guard comparisons + ~1,151 replacements
full sort comparisons, n*log2(n): ~232,534,967
edge cases
heap with fewer values than k=5 : [1, 2, 3]
quickselect, ties at the boundary : [7, 9, 9, 9]
heap, ties at the boundary : [7, 9, 9, 9]
#include <algorithm>
#include <cstdio>
#include <functional>
#include <numeric>
#include <random>
#include <vector>
static long long calls = 0;
int main() {
const size_t n = 200000, k = 100;
std::printf("g++ %s, n=%zu, k=%zu\n", __VERSION__, n, k);
std::mt19937 gen(8);
std::vector<int> random_order(n), ascending(n);
std::iota(random_order.begin(), random_order.end(), 0);
std::shuffle(random_order.begin(), random_order.end(), gen);
std::iota(ascending.begin(), ascending.end(), 0);
auto counting_less = [](int a, int b) { ++calls; return a < b; };
std::printf("%-13s%16s%16s%12s\n", "input", "nth_element", "full sort", "top-k ok");
for (auto& [name, data] : {std::pair<const char*, std::vector<int>>{"random order", random_order},
std::pair<const char*, std::vector<int>>{"ascending", ascending}}) {
std::vector<int> a = data;
calls = 0;
// Put the k largest in a[n-k..n): everything left of nth is <= nth, everything right is >= nth.
std::nth_element(a.begin(), a.end() - k, a.end(), counting_less);
long long select_calls = calls;
std::sort(a.end() - k, a.end());
std::vector<int> b = data;
calls = 0;
std::sort(b.begin(), b.end(), counting_less);
bool ok = std::equal(a.end() - k, a.end(), b.end() - k);
std::printf("%-13s%16lld%16lld%12s\n", name, select_calls, calls, ok ? "yes" : "NO");
}
return 0;
}
Output (g++ 14.2 in the python:3.12 container, compiled with g++ -O2 -std=c++17):
g++ 14.2.0, n=200000, k=100
input nth_element full sort top-k ok
random order 362007 4198328 yes
ascending 400127 4526699 yes
Reading the numbers
- Sort and slice costs 3,257,996 comparisons on random order at n = 200,000, which is about n log2 n; on 10 million values that is about 232 million comparisons (n log2 n from the last printed line), plus the whole dataset in memory. Timsort needs only 199,999 comparisons on already sorted or reversed input, so the cost depends on the data's order. In Python,
sorted()also copies the list, andlist.sort()can need a scratch array of up to n/2 slots. - Heap of size k costs 205,908 comparisons on random order (about 1.03 per value: one guard comparison per value, plus a few sifts), and 762 replacements, close to the k * ln(n/k) = 760 that the random-order argument predicts: for values in random order, the i-th value is equally likely to have any rank among the first i values, so the chance its rank is within the top k of those i is k/i, and the replacements are the sum of k/i over i from k to n. Since the sum of 1/i from k to n is about ln(n) - ln(k) = ln(n/k), the total is about k ln(n/k). On ascending input every value beats the root, so there are 199,900 replacements and 1,543,395 comparisons, which is the O(n log k) worst case: the printed breakdown for ascending input is 1,543,395 comparisons in total: the first heap build, 199,900 guard checks (one per value after the first 100), and the rest spent sifting inside the replacements. The sifting alone is about 6.7 comparisons per replacement, close to log2(100) = 6.64; adding the one guard comparison per value and the build gives the 7.72 overall per replacement that dividing the total by 199,900 produces. On 10 million values that is an estimate of about 10.3 million comparisons for random order and up to about 77 million for ascending order, extrapolated from these ratios, not measured.
- Quickselect (random pivot, counted as one comparison per element per round, plus one final filter pass to collect the winners) costs between 442,620 and 1,140,763 comparisons here. It reorders or copies the data; the shipped Python version builds new lists and uses O(n) extra memory.
std::nth_elementcosts 362,007 comparator calls on random order and 400,127 on ascending order, about 1.8n and 2.0n, against 4,198,328 and 4,526,699 forstd::sort. It works in place on the array and leaves the 100 largest in the last 100 positions, whichstd::sortthen orders. The C++ standard requires O(N) comparisons on average for it, not as a worst case (cppreference), and the implementation is typically introselect (quickselect that switches to a guaranteed-linear method when it makes poor progress), so the standard does not by itself promise a worst-case bound.
How to read the C++ program: calls is a global counter. counting_less is a lambda, a small unnamed function written inline, that adds one to calls and returns a < b; passing it as the comparator makes every comparison counted. std::iota fills a vector with 0, 1, 2, ... and std::shuffle with a fixed-seed generator gives a reproducible random order. The for (auto& [name, data] : {...}) loop walks a list of (label, vector) pairs and the square brackets unpack each pair into two names. std::nth_element(a.begin(), a.end() - k, a.end(), counting_less) rearranges a so the element at position n-k is in its sorted place with the k-1 larger ones after it; std::sort on the last k then orders just those 100, and std::equal checks them against the same slice of a fully sorted copy.
Memory for the real input
For 10 million doubles the printed arithmetic gives 80,000,000 bytes in a packed array('d'), 320,000,000 bytes as a Python list of float objects (an 8-byte slot plus a 24-byte object per value), and 800 bytes of slots for a heap of 100. If the numbers come from a file or a database cursor, the heap approach never needs the other 9,999,900 in memory at all; sorting and nth_element need the data loaded first.
Recommendation and what would change it
| Situation | Choice | Why |
|---|---|---|
| Values stream in, or loading all 10 million is costly | size-100 min-heap | O(k) memory, one pass, bounded worst case |
| 10 million doubles already in a mutable contiguous array, lowest latency wanted | nth_element, then sort the last 100 | about 2n comparisons, in place |
| You also need median, p99 and other positions on the same data | sort once | every position is then an index |
| Input must be safe from hostile ordering and you have only a fixed-pivot quickselect | heap | a first-element-pivot quickselect goes quadratic on sorted input (the first-element pivot line of the output) |
Edge cases and common mistakes
- Fewer than k values: the heap simply holds all of them; the code slices
values[:k]and loops over nothing. - Duplicates around the 100th value: the heap keeps exactly k items and the answer is the same multiset of values either way. Which of several equal copies stays is decided by the heap's internal layout, not by arrival order; if records with equal values must be resolved by arrival (earliest wins), push
(value, -position)pairs, since a later equal item then compares as smaller than the root and never replaces it. Quickselect fills the remainder with copies of the threshold. - Using a max-heap of all n values (heapify is O(n), but it needs all the data in memory and then 100 pops of O(log n) each): correct, but it gives up the memory advantage.
- Using
heapqas a max-heap without negating values: on Python 3.12heapqoffers only min-heap functions (public max-heap variants were added in Python 3.14), so push negated values or wrap them. - Comparing the options by wall-clock on a laptop instead of counting operations and checking memory.
Running the code
python:3.12 and its bundled g++ (standard library only)
python top_k_methods.py
g++ -O2 -std=c++17 -o nth_element_demo nth_element_demo.cpp && ./nth_element_demo
(save the first listing as top_k_methods.py and the second as nth_element_demo.cpp)
That is every published Sorting and Searching Algorithms question for Game Developer so far. Browse the other topics in this category, or practice this one interactively.