01 / The idea
Ask for one position, not a complete ranking.
The dashboard has 15 integer latency readings. For p90, the nearest-rank rule asks for
position ceil(90 × 15 / 100) = 14 in sorted order. The answer is 540 ms, but the algorithm
does not need to put all 15 readings in order to know that.
Quickselect keeps an interval of possible positions. A pivot lands at a final position after partitioning: smaller values are to its left, greater-or-equal values to its right. If the target is left of that position, the right side is irrelevant; if it is right, the left side is irrelevant.
The result is an order statistic and its record. It does not promise that neighboring readings are sorted, and it does not explain why a request was slow.
Find the percentile without ordering every reading.
p90 uses ceil(90 × 15 / 100): one position in
sorted order.
No sorting yet: keep the target rank and the unsorted readings.
Name the target rank
The nearest-rank p90 target is rank 14 of 15. We need one position, not a complete ordering.
Reduced motion: choose a scene to see its completed state.
Read this scene
The nearest-rank p90 target is rank 14 of 15. We need one position, not a complete ordering.
The nearest-rank p90 target is rank 14 of 15. We need one position, not a complete ordering. Target: rank 14 of 15.
Watch and Step through replay the same target rank, pivot, and discarded interval. Try it runs the TypeScript model on your edited readings.
Step through the rank, the pivots, and the discarded side. Then change the percentile or readings to see that the selected threshold can move while the partition rule stays the same.
02 / Name the rule
Partition once; discard what cannot contain the rank.
target = ceil(percentile × n ÷ 100) − 1
The target is a zero-based index: the 14th value of 15 sits at index 13. Start with left = 0 and right = n − 1. Choose a pivot from that interval,
partition it, and call its final position p. The pivot is the answer when p = target. Otherwise continue with right = p − 1 or left = p + 1.
Name one position
Make the percentile convention explicit before the first comparison.
Split the interval
Move smaller readings before the pivot and leave the pivot at its final position.
Keep one side
The target rank tells you which partition cannot matter anymore.
What about equal readings?Greater-or-equal belongs on the right
The teaching partition places values strictly smaller than the pivot on the left and equal values to its right. That still preserves the target value when duplicates exist; the selected record is one deterministic member of the equal-valued group.
Percentiles are policy, not a universal fact. Nearest rank is easy to explain here; an analytics pipeline may choose interpolation, an inclusive rank, or a weighted percentile instead.
03 / Follow one operation
Five pivots leave 540 ms at index 13.
The target is index 13, the 14th of 15 values. Here is the replay from the top of the page, one partition at a time:
- Pivot 680 ms, the slowest reading, lands at index 14. Nothing is to its right, so the next interval is indexes 0–13. 14 comparisons.
- Pivot 150 ms lands at index 5. Index 13 is to its right, so the five fast readings at 0–4 are dropped. 13 comparisons.
- Pivot 355 ms lands at index 11. Only 12–13 can still hold the target. 7 comparisons.
- Pivot 410 ms lands at index 12, leaving index 13 alone. 1 comparison.
- Pivot 540 ms is the only reading left, at index 13. It is the answer. 0 comparisons.
That is 35 comparisons, and the readings at indexes 0–4 and 6–10 were never put in order. The replay uses a seeded xorshift32 pivot source so every reader sees the same trace. The seed is for teaching and testing; the expected bound comes from pivot quality, not from this particular sequence.
04 / Read the shape
The selected value is the reusable boundary.
Basic form turns the percentile into an index and runs the partition loop on a copy of the readings. In the wild is the contract around that loop: errors, validation, the seeded pivot source, and the trace it returns. At the call site uses the selected value as an alert threshold and reports readings at or above it without asking for a full sorted list.
Turn the percentile into a zero-based index in integer arithmetic, copy the readings, and partition around seeded pivots, keeping only the side that holds the index.
export function percentileRank(count: number, percentile: number): number {
if (
!Number.isInteger(count) ||
count < 1 ||
!Number.isInteger(percentile) ||
percentile < 1 ||
percentile > MAX_PERCENTILE
)
throw new SelectError('bad-percentile', 'Percentile must be a whole number from 1 to 100.');
// Integer nearest rank: ceil(percentile × count / 100) − 1 without floating-point error.
return Math.floor((percentile * count + MAX_PERCENTILE - 1) / MAX_PERCENTILE) - 1;
}
export function selectPercentile(
values: Reading[],
percentile = DEFAULT_PERCENTILE,
seed = DEFAULT_SEED
): SelectionResult {
validateReadings(values);
if (!Number.isInteger(seed) || seed < 0 || seed > 0xffffffff)
throw new SelectError('bad-seed', 'Seed must be an unsigned 32-bit integer.');
const rank = percentileRank(values.length, percentile);
const order = values.map((reading) => ({ ...reading }));
const state = { value: seed || DEFAULT_SEED };
const steps: PartitionStep[] = [];
let comparisons = 0;
let lower = 0;
let upper = order.length - 1;
while (lower <= upper) {
const pivotIndex = lower + drawBelow(state, upper - lower + 1);
const pivotValue = order[pivotIndex].ms;
swap(order, pivotIndex, upper);
let boundary = lower;
let passComparisons = 0;
for (let index = lower; index < upper; index += 1) {
passComparisons += 1;
if (order[index].ms < pivotValue) {
swap(order, boundary, index);
boundary += 1;
}
}
swap(order, boundary, upper);
comparisons += passComparisons;
const discarded: PartitionStep['discarded'] =
rank < boundary ? 'upper' : rank > boundary ? 'lower' : 'none';
const nextLower = rank < boundary ? lower : rank > boundary ? boundary + 1 : boundary;
const nextUpper = rank < boundary ? boundary - 1 : rank > boundary ? upper : boundary;
steps.push({
step: steps.length + 1,
lower,
upper,
pivotIndex,
pivotValue,
boundary,
comparisons: passComparisons,
snapshot: order.map((reading) => ({ ...reading })),
discarded,
nextLower,
nextUpper
});
if (rank === boundary)
return {
percentile,
rank,
value: order[boundary].ms,
selectedId: order[boundary].id,
steps,
comparisons,
order
};
lower = nextLower;
upper = nextUpper;
}
throw new SelectError('bad-percentile', 'The requested rank was not reachable.');
}
function swap(values: Reading[], left: number, right: number): void {
[values[left], values[right]] = [values[right], values[left]];
}func PercentileRank(count, percentile int) (int, error) {
if count < 1 || percentile < 1 || percentile > maxPercentile {
return 0, &SelectError{Code: BadPercentile, Message: "percentile must be a whole number from 1 to 100"}
}
// Integer nearest rank: ceil(percentile × count / 100) − 1 without floating-point error.
return (percentile*count+maxPercentile-1)/maxPercentile - 1, nil
}
func SelectPercentile(values []Reading, percentile int, seed uint32) (SelectionResult, error) {
if err := validateReadings(values); err != nil {
return SelectionResult{}, err
}
rank, err := PercentileRank(len(values), percentile)
if err != nil {
return SelectionResult{}, err
}
if seed == 0 {
seed = defaultSeed
}
order := cloneReadings(values)
state := randomState{value: seed}
steps := []PartitionStep{}
comparisons := 0
lower, upper := 0, len(order)-1
for lower <= upper {
pivotIndex := lower + state.drawBelow(upper-lower+1)
pivotValue := order[pivotIndex].MS
swap(order, pivotIndex, upper)
boundary := lower
passComparisons := 0
for index := lower; index < upper; index++ {
passComparisons++
if order[index].MS < pivotValue {
swap(order, boundary, index)
boundary++
}
}
swap(order, boundary, upper)
comparisons += passComparisons
discarded := "none"
nextLower, nextUpper := lower, upper
if rank < boundary {
discarded = "upper"
nextUpper = boundary - 1
} else if rank > boundary {
discarded = "lower"
nextLower = boundary + 1
} else {
nextLower, nextUpper = boundary, boundary
}
steps = append(steps, PartitionStep{
Step: stepsToNumber(steps), Lower: lower, Upper: upper, PivotIndex: pivotIndex,
PivotValue: pivotValue, Boundary: boundary, Comparisons: passComparisons,
Snapshot: cloneReadings(order), Discarded: discarded,
NextLower: nextLower, NextUpper: nextUpper,
})
if rank == boundary {
return SelectionResult{
Percentile: percentile, Rank: rank, Value: order[boundary].MS,
SelectedID: order[boundary].ID, Steps: steps, Comparisons: comparisons,
Order: order,
}, nil
}
lower, upper = nextLower, nextUpper
}
return SelectionResult{}, &SelectError{Code: BadPercentile, Message: "the requested rank was not reachable"}
}
func stepsToNumber(steps []PartitionStep) int { return len(steps) + 1 }
func swap(values []Reading, left, right int) {
values[left], values[right] = values[right], values[left]
}Reading the TypeScriptThe target rank controls the next bounds
The implementation records a snapshot after each partition so the story can expose the
active interval. The exported function copies the input first; an in-place version can
remove that copy when mutation is part of its contract. The target index is computed in
integers, (percentile × n + 99) / 100 − 1 rounded down, so floating point can’t
turn 0.28 × 25 into 7.000000000000001 and move the rank.
Reading the GoThe pivot trace stays reproducible
Go uses the same xorshift32 transitions, rejection-safe bounded draw, strict comparison, and nearest-rank formula. The fixture output therefore agrees without hiding language-level data types.
What is refusedBound the teaching surface
Both versions accept at most 64 uniquely named readings, whole milliseconds from 0 to 60,000, and whole percentiles from 1 to 100. Invalid input is rejected before the partition can return a partial answer.
05 / Try a decision
Which side can still hold the 14th value?
Partition 3 from the replay is the moment to check. The pivot has just landed, and the target index decides which side the next partition works on.
Once the side is chosen, the answer is a value, and a threshold is not a diagnosis. A p90 threshold answers “which readings sit in the slowest ten percent under this policy?” It does not answer whether the service breached a target, whether a user experienced the delay, or what caused it.
Operational rule: use Quickselect when one rank is enough, then route the selected records into the investigation or alerting policy that gives the number meaning.
Try three policy changesThe algorithm cannot choose the policy
- p50: describe a typical middle reading, not a tail alert.
- p99: use a larger sample if the tail should be stable; small batches make it jumpy.
- Interpolation: if the dashboard promises a value between observations, change the percentile contract rather than quietly changing Quickselect's rank.
06 / Follow the cost
Expected linear work trades away a complete order.
Random pivots shrink the active interval in expectation, so one selection is expected O(n). An unlucky sequence of extreme pivots can make the passes cost O(n²). A full sort pays O(n log n), but leaves every rank available for later questions. The code on this page also copies the whole order after every partition so the film can replay it. That trace is a teaching cost, and the table lists it on its own row.
| Operation | Time | Extra space | What it assumes |
|---|---|---|---|
| Choose the nearest-rank target | O(1) | O(1) | The count and percentile policy determine one zero-based target rank. |
| Partition one active interval | O(k) | O(1) | Compare each of k active readings with the chosen pivot once. |
| Quickselect partitions, expected | O(n) | O(n) | Random pivots shrink the interval in expectation. The O(n) space is the one copy that keeps the caller’s array unchanged; an in-place form uses O(1) extra. |
| Quickselect partitions, worst case | O(n²) | O(n) | Repeatedly choosing an extreme pivot leaves almost the whole interval for the next pass. |
| Record the replay trace (this lesson) | O(n) per partition | O(n) per partition | Each partition stores a full copy of the order for the film: expected O(n log n) time and space in total, O(n²) in the worst case. Drop the snapshots and the rows above are the whole cost. |
| Sort, then read one rank | O(n log n) | O(n) or O(log n) | The baseline orders every value, which is useful when the complete order will be reused. |
07 / Give it a real job
A latency dashboard needs one p90 per window.
A metrics service collects request times for each endpoint and, once a minute, closes the
window and asks for its p90. That is one rank per window, and it is asked over and over, so
sorting every batch pays for 15 positions to use one. chooseAlertThreshold in At the call site is that call: it selects 540 ms and lists the readings at
or above it, export and billing, for the alert to show.
Quickselect owns the rank and nothing else. The percentile convention, the alert target, and what counts as slow belong to the dashboard’s policy. It also needs the whole window in memory. When a window holds millions of readings, metrics systems usually keep a histogram or a sketch instead and read an approximate p90 from it.
This runs in the metrics service that closes each window; the dashboard page receives the threshold and the flagged readings, and nothing in a component computes them.
08 / Make the call
Choose by how much order you actually need.
Use Quickselect for one or a few order statistics in a batch, especially when a complete sorted copy would be wasted. Use a full sort when readers need the ranking, tie order, or many later percentile queries.
Use Welford for a running mean and variance when the stream is live and no rank is required. Use reservoir sampling when the problem is keeping a uniform bounded sample from an unknown stream, not selecting a percentile from the full batch.
Three boundaries to rememberSelection is not sorting or statistics policy
- Not sorting: only the target's rank is fixed; neighbors may be in any order.
- Not streaming: this contract sees the batch. A live stream needs a different summary or storage policy.
- Not a percentile definition: nearest rank, interpolation, weights, and missing-value rules belong to the caller.
09 / Take the idea with you
Explain a p90 without saying “Quickselect.”
“Name the one position you want. Pick a value, put everything smaller on its left and the rest on its right, and see where it lands. If your position is on the left, forget the right, and the other way round. When the value you picked lands on your position, that is the answer.”
Before moving on, write down ten numbers you know, like your last ten commute times. Pick the fifth as a pivot, partition by hand, and count how many numbers you never had to put in order to find the 9th smallest.
Connections to follow nextRelated lessons
- Sorting is the baseline: pay once, and every rank is there for the next question.
- Binary heap keeps the few largest in order as they arrive, when you want the ten slowest requests rather than one rank.
- Reservoir sampling keeps a fair, bounded sample of a stream too long to hold, so a percentile can be read from the sample.