skip to content

To keep the top 100 of a million C++ scores, when do you choose std::partial_sort, std::nth_element or a full std::sort?

level: seniorimportance: should knowfreq 45%

answer

  1. you only need K of N
  2. N log K versus linear
  3. ordered top or just membership
  4. the nth position is exact

basics

~20 s

std::nth_element finds the top 100 as an unordered set, or the 100th score, in linear time on average. std::partial_sort also ranks them, at about N log K comparisons. A full std::sort is for when every rank is needed.

solid answer

~50 s

`std::partial_sort(first, first + k, last, comp)` places the `k` best elements, sorted, in `[first, first + k)` and leaves the rest in unspecified order, at roughly `N log K` comparisons. `std::nth_element(first, first + k - 1, last, comp)` puts exactly the element that would be at position `k - 1` after a full sort there, with no element before it ranking after it and none after it ranking before; the top `k` are then in `[first, first + k)` but **unsorted**, and the standard requires only linear time on average. For a leaderboard that needs the 100 best in rank order, `nth_element` followed by `std::sort` of the first 100 is usually at least as fast as `partial_sort` for large `N`; for a cutoff score or an unordered top set, `nth_element` alone is enough. A full `std::sort` costs `N log N` and is right only when you need every rank. Neither selection algorithm is stable.

code

cpp · 26 lines
cpp
#include <algorithm>
#include <functional>
#include <iostream>
#include <random>
#include <vector>

int main() {
    std::vector<int> scores(1'000'000);
    std::mt19937 gen(7);
    std::uniform_int_distribution<int> dist(0, 9'999'999);
    for (int& s : scores) s = dist(gen);
    const std::ptrdiff_t k = 100;

    // A: top 100 in rank order, rest unspecified
    std::vector<int> a = scores;
    std::partial_sort(a.begin(), a.begin() + k, a.end(), std::greater<>{});

    // B: top 100 in unspecified order; a.begin()[k-1] is the 100th best
    std::vector<int> b = scores;
    std::nth_element(b.begin(), b.begin() + (k - 1), b.end(), std::greater<>{});
    int cutoff = b[k - 1];
    std::sort(b.begin(), b.begin() + k, std::greater<>{});  // only if order is needed

    std::cout << "cutoff " << cutoff << " same=" << std::equal(a.begin(), a.begin() + k, b.begin())
              << " is100th=" << (a[k - 1] == cutoff) << '\n';
}

go deeper

for a junior

Know that you do not need a full sort to get the best few elements: partial_sort and nth_element exist for that.

for a middle

Explain what each leaves sorted and unspecified, and their costs: about N log K for partial_sort, linear on average for nth_element.

for a senior

Pick per requirement: nth_element for a cutoff or set, nth_element plus a small sort for an ordered top-k, a bounded heap for streaming, and measure on real sizes.

for a principal

Decide whether rankings are recomputed in batches or maintained incrementally, trading CPU per query against update cost and memory.

## The problem A game server holds a million scores and must publish the top 100. Sorting all of them works, but it orders 999,900 elements nobody looks at. `<algorithm>` has two selection algorithms that do less work, and choosing between them depends on what the caller needs: the top set, the top set in order, or one cutoff value. ## std::partial_sort `std::partial_sort(first, middle, last, comp)` puts the `middle - first` smallest elements (under `comp`) into `[first, middle)`, **sorted**, and leaves `[middle, last)` in an unspecified order. The standard specifies approximately `(last - first) * log(middle - first)` comparisons. Implementations typically build a heap of the first `k` elements, push each remaining element through it when it beats the heap's worst, and finish with a heap sort of the `k` winners, which is where the `N log K` shape comes from. With `std::greater<>{}` the "smallest" become the highest scores: ```cpp std::partial_sort(v.begin(), v.begin() + 100, v.end(), std::greater<>{}); ``` `std::partial_sort_copy` does the same into a separate destination range, leaving the input untouched. ## std::nth_element `std::nth_element(first, nth, last, comp)` guarantees three things: - `*nth` is the element that would be there if the whole range were sorted; - for every iterator `i` before `nth` and every `j` at or after it, `comp(*j, *i)` is false, so nothing after the split ranks ahead of anything before it; - nothing else: both sides are in unspecified order. The standard requires the sequential version to be **linear on average**. libstdc++ implements it as introselect: quickselect partitioning with a depth limit that falls back to heap selection, which keeps the worst case under control. To get the top 100, pass `nth = first + 99`: positions 0 to 99 then hold the 100 best, in no particular order, and `v[99]` is the 100th-best score - the cutoff. ## Choosing | Need | Call | Cost (comparisons) | |---|---|---| | Cutoff score only (the 100th best) | `nth_element` | linear on average | | The top 100 as a set (any order) | `nth_element` | linear on average | | The top 100 in rank order | `nth_element` then `sort` the first 100, or `partial_sort` | about `N + K log K` versus about `N log K` | | Every rank | `sort` | `N log N` | | The median | `nth_element` at `first + N/2` | linear on average | For `K` much smaller than `N` the two ordered-top approaches are close; for larger `K` the `nth_element`-then-`sort` combination wins because the `log K` factor applies to only `K` elements. Measure on your data before committing - the constants differ between implementations. ## A worked example Suppose the server must publish the top 100 every minute from one million scores: 1. Copy the scores if their stored order matters elsewhere. 2. Call `std::nth_element(v.begin(), v.begin() + 99, v.end(), std::greater<>{})`. Afterwards `v[99]` is the 100th-best score - the cutoff for the "top 100" badge - and `v[0]` to `v[98]` are the 99 scores at least that high, in no particular order. 3. Call `std::sort(v.begin(), v.begin() + 100, std::greater<>{})` to rank those 100 for display. The first step touches every element a small number of times on average; the second sorts only 100. Compared with `std::sort` on all one million, the work drops from roughly 20 comparisons per element to a few. If only the badge cutoff is needed, step 3 disappears entirely. ## Pitfalls 1. **Off-by-one on `nth`.** The 100th element is at index 99. Passing `first + 100` makes `v[100]` the 101st-best and the top 100 still occupies `[0, 100)` - correct for the set, wrong for the cutoff. 2. **Expecting order from `nth_element`.** The top elements are partitioned, not sorted. Code that prints `v[0]` as the winner after `nth_element` alone is wrong. 3. **Expecting stability.** Neither algorithm preserves the order of equal scores; add a tie-breaker key if rank among ties matters. 4. **Mutating the source.** Both algorithms reorder the input. Copy first, or use `partial_sort_copy`, when the original order must survive. 5. **Streaming data.** If scores arrive one at a time and the top 100 must always be current, a bounded heap (a `std::priority_queue` of size 100) maintained per insertion avoids re-selecting over the whole set.

  • After std::nth_element(v.begin(), v.begin() + 99, v.end(), std::greater<>{}), what can you say about v[0]?
    Only that it is one of the 100 highest scores. `nth_element` guarantees the exact element at index 99 and that nothing in `[0, 99)` ranks below it, but the first 99 positions are in unspecified order. To publish the leader you must still sort the first 100, or call `std::max_element` on them.
  • How would you keep a top-100 list current while scores keep arriving?
    Maintain a min-heap of at most 100 entries, for example a `std::priority_queue<int, std::vector<int>, std::greater<>>`. For each new score, push it if the heap holds fewer than 100, otherwise replace the top when the new score beats it. Each update costs `O(log 100)`, and the full ranking is produced by sorting the 100 entries only when it is requested.

  • Saying std::nth_element leaves the first k elements sorted
  • Sorting a million elements to read the first 100
  • Passing first + k instead of first + k - 1 to get the kth value
  • Claiming partial_sort keeps equal scores in input order
  • Stating nth_element is guaranteed linear in the worst case by the standard