---
name: sorting-and-order-statistics
description: Use when choosing or analyzing sorting, heaps, priority queues, linear-time integer/distribution sorting, quicksort, selection, medians, quantiles, top-k, or order-statistic algorithms under practical engineering constraints.
license: MIT
---

# Sorting and Order Statistics

## Overview

Use sorting and selection as engineering tools, not reflexes. The core move is to identify the exact order information required, then choose the weakest ordering primitive that satisfies it under the real key, stability, memory, and adversary constraints.

## Shared CLRS Conventions

Follow the parent `clrs` skill for mathematical formatting, formula-free headings, direct polished answers, and CLRS-wide answer style.

## When to Use

- You need to sort records, select a percentile, maintain top-k, merge sorted streams, or implement a priority queue.
- A prompt involves heaps, heapsort, quicksort, counting sort, radix sort, bucket sort, medians, quantiles, or ith order statistics.
- A comparison-sort lower bound seems relevant, or a proposed linear-time sort depends on integer keys, digits, or distribution assumptions.
- An implementation must preserve satellite data, stability, handles, index maps, or large-payload locality.

Do **not** use this skill merely because output should appear sorted in a UI. Use the platform's ordinary sort unless algorithm choice, asymptotics, stability, or data-structure behavior matters.

## First Decision: How Much Order Do You Need?

| Need | Prefer | Why |
| --- | --- | --- |
| General ordered records | Library sort, stable sort if ties matter | Production sorts are engineered for cache, duplicates, depth limits, and language semantics |
| Stable order by small dense integer key | Counting sort or radix sort | Beats comparison sorting only because key values can index counts or digits |
| Dynamic repeated min/max | Binary heap priority queue | Maintains partial order, not full sorted order |
| Merge k sorted streams | Min-heap of stream heads | Gives total cost based on k, not total stream count as a sort key |
| Single rank, median, percentile threshold | Selection or `nth_element` | Full sorting pays for order you will discard |
| Top-k unsorted | Size-k heap or selection threshold | Choose by k size, streaming needs, and memory |
| Top-k sorted | Select threshold, partition top-k, then sort only k | Avoids sorting the cold majority |
| Worst-case linear rank guarantee | Median-of-medians SELECT | Usually a fallback or proof tool because constants are high |

Before accepting a sort proposal, ask:

1. Is the output required to be fully ordered, or only partitioned around a rank or key?
2. Are equal-key records required to preserve input order?
3. Are keys comparison-only, bounded integers, fixed-width digits, or drawn from a known distribution?
4. Is moving the record payload expensive enough to sort pointers, indices, or references instead?
5. Can the input be adversarial, highly duplicated, already sorted, skewed, or streaming?

## Comparison Sorting Boundary

For comparison sorts on distinct keys, the decision-tree lower bound is:

$$
\Omega(n\lg n)
$$

because all permutations must remain possible leaves. This lower bound does **not** apply when the algorithm uses key values as array indices, digit values, or distribution positions. Whenever an answer claims linear sorting, state which non-comparison assumption paid for it.

## Practical Sorting Choices

| Algorithm family | Use when | Avoid or qualify when |
| --- | --- | --- |
| Insertion sort | Small arrays, nearly sorted runs, final cutoff inside engineered sorts | Large arbitrary inputs; worst case is quadratic |
| Merge sort or stable library sort | Stability is required and extra memory is acceptable | In-place memory is mandatory |
| Heapsort | In-place worst-case comparison bound is more important than constants/cache behavior | You want the fastest ordinary production sort |
| Quicksort partitioning | Teaching, `nth_element`, partition-based selection, or controlled internal implementation | Hand-rolled quicksort in production |
| Counting sort | Integer key domain is small or remapped densely; stability matters | Key range is huge or sparse relative to input |
| Radix sort | Large batches of fixed-width primitive keys, IDs, or strings with stable digit passes | Memory bandwidth, allocation, or complex comparators dominate |
| Bucket sort | Distribution is validated and bucket boundaries are chosen from probability mass | Skew is unknown; worst-case guarantees matter |

Industrial default: use a mature library sort unless a property above clearly beats it. If implementing quicksort-like code, protect against duplicates with 3-way partitioning, protect against fixed bad input orders with randomized or sampled pivots, use a small-array insertion cutoff, and add a depth-limited fallback for worst-case executions. Random pivoting changes which inputs are predictably bad; it does not make worst cases impossible, and it does not by itself fix equal-key collapse. Tail recursion elimination only protects the stack if the smaller side is recursed into and the larger side is iterated.

## Stability, Satellite Data, and Payload Movement

Sorting keys usually means sorting records. In production, keys travel with satellite data.

- If equal keys must retain arrival, timestamp, or file order, require a stable algorithm or explicitly add a stable tie-breaker.
- If records have large payloads, prefer sorting indices, pointers, row IDs, or compact key-reference pairs, then gather or stream the payload once.
- Counting sort is stable when placement processes input from the end while decrementing prefix counts; stable bucket construction preserves order by appending to buckets in input order.
- Radix sort needs a stable digit sort; without stability, later digit passes destroy earlier digit order.
- Bucket sort's average linear claim depends on distribution assumptions; counting sort's linear claim depends on key-range assumptions, not uniformity.

## Heaps and Mutable Priority Queues

A heap is a partial order for repeated extrema. It is the right abstraction for schedulers, event simulation, Dijkstra-like algorithms, k-way merge, streaming top-k, and dynamic priorities.

Binary heap facts:

- Root is min or max depending on orientation.
- Leaves occupy the second half of the array.
- `heapify` assumes child subtrees are already heaps and moves one bad node downward.
- Building a heap bottom-up is linear because most nodes are near leaves; do not multiply every node by the root height.

| Heap operation | Cost | Implementation note |
| --- | --- | --- |
| Peek min or max | Constant | Read the root without changing the heap |
| Insert | Logarithmic | Append, then bubble up |
| Extract min or max | Logarithmic | Move the last element to the root, then heapify down |
| Increase or decrease key | Logarithmic | Choose direction from heap orientation and priority change |
| Build heap bottom-up | Linear | Start at the last internal node and heapify downward |

Mutable priority queue checklist:

1. Store a map from external handle or job ID to heap index.
2. Every array swap must update both affected map entries in the same helper.
3. Reject duplicate live IDs, or define update semantics explicitly.
4. On extraction or cancellation, delete the removed ID from the map and invalidate stale handles.
5. After moving the last heap element into a hole, compare with its parent and best child to choose bubble-up or heapify-down. If uncertain, perform the direction that fixes the violated local relation, then assert the heap property in debug builds.
6. For a min-heap, a numerically smaller priority bubbles up; a numerically larger priority heapifies down. Reverse this for max-heaps.

Do not expose raw indices as durable handles unless they carry generation/version checks. Stale handles cause silent scheduler corruption.

## Selection and Order Statistics

The ith order statistic is the ith smallest element. Selection does not need to order all pairs, so the sorting lower bound does not apply.

Use this workflow:

1. Translate the requested percentile, median, threshold, or top-k into a rank convention.
2. If only the threshold is needed, use selection or a library `nth_element`/partition primitive.
3. If the top-k values are needed but not sorted, use a size-k heap for streaming data or selection plus partition for batch data.
4. If sorted top-k output is needed, sort only the selected k elements.
5. If adversarial worst-case linear time matters, use median-of-medians as a fallback, not as the everyday fastest path.

Quickselect partitions around a pivot and recurses only into the side containing the desired rank. Its expected time is linear with random pivots, but worst case is quadratic. Median-of-medians spends linear work to choose a pivot that leaves at most a constant fraction of the input alive, giving worst-case linear time with larger constants.

Useful patterns:

- Simultaneous min and max: compare items in pairs, then compare the smaller to the current min and the larger to the current max.
- Largest k sorted: full sort is simple, heap extraction costs based on k, selection plus sorting k is often best for batch data when k is small.
- k quantiles: recursively select pivots to split ranks.
- Median or weighted median minimizes one-dimensional absolute deviation; for Manhattan distance in two dimensions, solve the coordinates independently.

## Linear-Time Sorting Preconditions

| Claim | Required precondition | Failure mode |
| --- | --- | --- |
| Counting sort is linear | Key range size is acceptable after remapping | Huge sparse range burns memory |
| Counting sort is stable | Placement scans input in reverse or otherwise preserves equal-key order | Records with equal keys reorder |
| Radix sort is linear | Fixed digit count and stable digit sort with manageable digit range | Unstable pass corrupts prior digits |
| Bucket sort is average linear | Inputs are independent and approximately uniform after any transform | Skew collapses into one bucket |
| Selection is linear expected | Randomized or robust pivot strategy; only rank/partition is needed | Full sorted order still requires more work |

When assumptions are empirical, validate and monitor them. A nightly job using bucket boundaries should record bucket-size skew; a radix pass should be justified by actual key width and memory bandwidth; a counting sort should check that the count array is small enough for cache and memory.

## Invariant and Proof Recipes

- **Heapify:** Assume child subtrees are heaps; prove the only possible violation follows the moved node downward until the parent-child relation holds.
- **Build heap:** Loop downward from the last internal node; invariant says every later node is already the root of a heap.
- **Partition:** Name the regions less than, equal to, greater than, unknown, and pivot. The proof is the maintenance of those regions, not the pivot folklore.
- **Randomized quicksort analysis:** Define pair indicators. Two elements are compared only if one is the first pivot chosen from their rank interval; sum probabilities by linearity of expectation.
- **Counting sort stability:** Prefix counts identify final slots for each key; scanning from the end assigns equal keys from right to left so earlier records land earlier.
- **Selection:** Track the rank of the pivot within the current subarray and translate the target rank when recursing into the right side.
- **Median-of-medians:** Show enough elements are guaranteed below and above the pivot, then solve the shrink recurrence rather than claiming the pivot is exactly central.

## RED Pressure Failures This Skill Prevents

| Baseline failure | Required correction |
| --- | --- |
| Choosing textbook quicksort for stable 16-bit record sorting because it is in-place | Prefer stable counting/radix-style sorting or reference sorting; quicksort is unstable and moves payloads too much |
| Saying bucket sort needs uniform region codes for a dense integer key job | Counting sort needs a bounded key range, not uniformity; bucket sort needs distribution assumptions |
| Sorting all telemetry samples for a percentile and top-k | Select the percentile threshold and use heap or selection for top-k; sort only the top-k if ordered output is needed |
| Claiming p95 and top-k can always be solved in one ordinary streaming pass | Streaming top-k is easy with a heap; exact percentile generally needs stored data, sketches, multiple passes, or a selection-capable batch |
| Updating heap array swaps without map updates | Centralize swap-with-index-update and invalidate removed handles |
| Applying heapify in the wrong direction after priority changes | For min-heaps, smaller priority bubbles up and larger priority moves down; inspect both local relations after arbitrary removal |

## Common Mistakes

| Mistake | Correction |
| --- | --- |
| Treating quicksort as the practical lesson of the chapter | Extract partition balance, randomization, duplicate handling, adversarial input, and library-sort judgment |
| Applying the comparison-sort lower bound to counting or radix sort | State that these algorithms use key values, not only comparisons |
| Forgetting satellite data | Decide whether to move records, references, or compact key-reference pairs |
| Ignoring stability | Make equal-key order a first-class requirement when records, timestamps, or radix passes are involved |
| Using a heap as a complete sorted order | A heap gives repeated extrema and partial order; extracting all elements is a sort |
| Assuming randomized algorithms remove worst cases | They remove fixed-input dependence under the random model; worst-case executions still exist |
| Trusting average bucket performance without monitoring skew | Validate distribution and choose fallback behavior |

## Verification Pressure Tests

Use these to check future answers:

1. **Stable dense-key records:** For many large records with a small integer key and required tie order, the answer should reject textbook quicksort and discuss stable counting/radix/reference movement.
2. **Percentile and top-k:** For a large telemetry batch needing p95 and top-k, the answer should avoid full sorting unless a complete order is actually required.
3. **Mutable heap handles:** For a scheduler heap with arbitrary cancellation, the answer should require map updates on every swap and stale-handle defenses.
4. **Linear-time claim:** For counting, radix, or bucket sort, the answer should name the exact assumption that escapes the comparison lower bound.