Partial sorting

Why it matters

Often you do not need the whole list in order. A game shows the top ten scores. A teacher wants the median mark. A shop wants the third most expensive item. In each case, a full sort does more work than the task needs. The rest of the list is sorted for no reason.

C++ gives three tools for this. They are in the <algorithm> header, the same header as std::sort:

• std::partial_sort sorts only the first part of a range, such as the top three.
• std::nth_element places one chosen value at its correct position, and splits the rest without sorting either side.
• std::partial_sort_copy copies the sorted first part into a second list, and leaves the original list alone.

The main skill is knowing what each call promises about the rest of the list. Each one promises something different. A program that assumes the wrong promise gives wrong answers, and the mistake is easy to miss because the output looks almost right.

This lesson assumes you know how to sort a vector with std::sort and how to write a comparator. The earlier lessons covered both. Comparators in this lesson follow the rules from the comparison contracts lesson, so every comparator uses < or >, never <= or >=.

The idea: sort less than everything

Think about finding the three tallest students in a class of thirty. You could line up all thirty students by height, then read the first three. That works, but it orders the other twenty-seven for no reason. A quicker way is to walk down the line once and keep track of the three tallest you have seen so far. You never need to order the other students.

Partial sorting works in the same way. Each tool does less work than a full sort, and the less work it does, the less it promises about the rest.

Here is the ordering of the three promises, from strongest to weakest:

1. A full sort (std::sort) promises that the whole list is in order.
2. std::partial_sort promises that the first part of the list is in order, and that those values are the smallest in the list. It makes no promise about the rest.
3. std::nth_element promises that one position holds the value it would hold in a full sort, that everything to its left is not bigger, and that everything to its right is not smaller. It makes no promise about the order inside either side.

The standard asks for work close to n log k comparisons for std::partial_sort, where n is the list size and k is how many sorted positions you ask for. For std::nth_element it asks for about n comparisons on average. These are guidelines for speed, and the exact count depends on the data. What matters for a beginner is that both tools are faster than a full sort when k is small compared with n.

Worked example 1: the top three with std::partial_sort

std::partial_sort takes three iterators. The first is the start of the range. The middle marks how many positions you want sorted. The last is the end of the range.

partial_sort(first, middle, last);

After the call, the positions from first up to middle hold the smallest values, in order. "Smallest" means first in the order the comparator sets, so with greater<int>() these are the largest values, in descending order. The positions from middle to last hold the other values in some order. You cannot rely on that order.

The program below sorts a list of ten scores and prints the top three. It also prints the whole list afterwards, so you can see what the rest looks like.

#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
void show(const string& label, const vector<int>& v) {
    cout << label << ":";
    for (int x : v) cout << " " << x;
    cout << "\n";
}
 
int main() {
    vector<int> scores = {72, 95, 61, 88, 90, 55, 79, 99, 83, 67};
 
    vector<int> top3 = scores;
    partial_sort(top3.begin(), top3.begin() + 3, top3.end(), greater<int>());
    show("partial_sort top 3 (largest first)", top3);
    return 0;
}

The output is:

partial_sort top 3 (largest first): 99 95 90 61 72 55 79 88 83 67

The first three numbers are 99, 95 and 90, in that order. The other seven are the leftover numbers in no particular order. The 61, 72, 55 part is not sorted, and neither is the rest. That is correct behaviour. The call did only the work the task needed.

The middle argument is top3.begin() + 3. It means "the first three positions". The name middle is a little misleading, because the sorted part is not always the middle of the list. It is the front part, from the start up to the middle position. You will get the right answer if you read it as "the number of positions to sort".

Worked example 2: std::nth_element for the middle value

std::nth_element takes a range and one position called nth. The value at nth ends up exactly where it would be if the whole list were sorted. Everything before nth is no bigger than that value, and everything after nth is no smaller. Neither side is sorted.

nth_element(first, nth, last);

This is exactly what you need for a median. The median of an odd-sized list is the value in the middle position when the list is sorted. You can get it without sorting.

The program below extends the scores example. It finds the middle value and shows the whole list, so you can see the split.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
void show(const string& label, const vector<int>& v) {
    cout << label << ":";
    for (int x : v) cout << " " << x;
    cout << "\n";
}
 
int main() {
    vector<int> scores = {72, 95, 61, 88, 90, 55, 79, 99, 83, 67};
 
    vector<int> mid = scores;
    nth_element(mid.begin(), mid.begin() + mid.size() / 2, mid.end());
    show("nth_element, middle position", mid);
    cout << "median position value: " << mid[mid.size() / 2] << "\n";
    return 0;
}

The output is:

nth_element, middle position: 67 55 61 79 72 83 88 90 99 95
median position value: 83

The value at position 5 is 83. The list has ten values, so the middle position is index 5, which is the sixth value from the left. Check it against a full sort. The sorted list is 55, 61, 67, 72, 79, 83, 88, 90, 95, 99, and index 5 holds 83. The two results agree.

Now look at the left side. It holds 67, 55, 61, 79 and 72. Every one of these is below 83. The right side holds 88, 90, 99 and 95, and every one of these is above 83. The sides are split correctly, but neither side is in order. The left side starts with 67, then 55, which goes down before it goes up. That is allowed.

This is the most common source of confusion with std::nth_element. Beginners often read the output and think the list is sorted. It is not. Only the chosen position is correct.

Worked example 3: std::partial_sort_copy into a second list

Sometimes the original list must stay as it is. For example, the list may be shared with another part of the program, and you want only the top results in a new list. std::partial_sort_copy does this. It reads the original list, writes the sorted smallest values into a second list, and leaves the original unchanged.

partial_sort_copy(first, last, result_first, result_last);

The result list must already have a size. The function writes into the positions you give it, and it does not grow the list. It writes as many values as fit, and it returns an iterator to the position after the last value it wrote. If the result list is bigger than the input, only the input's values are written, and the leftover positions are not touched.

The program below asks for the top two scores from a list of four. The result list has two positions, so the function writes two values.

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector<int> scores = {64, 91, 78, 85};
 
    vector<int> best(2);
    partial_sort_copy(scores.begin(), scores.end(), best.begin(), best.end(), greater<int>());
 
    cout << "top 2 copy:";
    for (int x : best) cout << " " << x;
    cout << "\n";
    cout << "original:";
    for (int x : scores) cout << " " << x;
    cout << "\n";
    return 0;
}

The output is:

top 2 copy: 91 85
original: 64 91 78 85

The copy holds the two largest values in descending order. The original is unchanged. The function returns an iterator, which this program ignores. If you need to know how many values were written, store the return value and subtract the start of the result list from it.

Worked example 4: records with a comparator

The tools work with records too, not only with plain numbers. The comparator decides what "top" means. This example ranks players by points, highest first. When two players have the same points, the one whose name comes first in the alphabet ranks higher. The comparator uses the rule from the comparison contracts lesson: it compares points first, then names, and each step uses a strict < or >.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
struct Player {
    string name;
    int points;
};
 
int main() {
    vector<Player> players = {
        {"Asha", 14}, {"Ben", 22}, {"Chen", 9}, {"Dita", 22},
        {"Emil", 17}, {"Farah", 3}, {"Gus", 17}, {"Hana", 11}};
 
    auto better = [](const Player& a, const Player& b) {
        if (a.points != b.points) return a.points > b.points;
        return a.name < b.name;
    };
 
    partial_sort(players.begin(), players.begin() + 3, players.end(), better);
    cout << "top 3:\n";
    for (size_t i = 0; i < 3; i++)
        cout << "  " << players[i].name << " " << players[i].points << "\n";
 
    vector<Player> all = {
        {"Asha", 14}, {"Ben", 22}, {"Chen", 9}, {"Dita", 22},
        {"Emil", 17}, {"Farah", 3}, {"Gus", 17}, {"Hana", 11}};
    size_t mid = all.size() / 2;
    nth_element(all.begin(), all.begin() + mid, all.end(), better);
    cout << "player at the middle rank: " << all[mid].name << " " << all[mid].points << "\n";
    cout << "ranked above it:";
    for (size_t i = 0; i < mid; i++) cout << " " << all[i].name;
    cout << "\n";
    return 0;
}

The output is:

top 3:
  Ben 22
  Dita 22
  Emil 17
player at the middle rank: Asha 14
ranked above it: Emil Ben Dita Gus

The top three are Ben and Dita, who both have 22 points, and then Emil. Emil comes before Gus because the names are compared when the points tie. The middle rank of eight players is position 4, which holds Asha with 14 points. The four players above Asha are the ones with higher points, but in an order that the call does not promise. The output shows Emil first and Ben second, which is not the order a full sort would give. The rank is correct, and the order above it is not.

Notice that the all list is built again before the nth_element call. Each call changes the list it is given. If you want to run a second tool on the same data, copy the data first, or the second call sees the list in the state the first call left it.

Worked example 5: a k-th largest value and the ranges versions

Sales figures are a good example of a "k-th largest" question. Suppose you want the fourth largest sale. The following program uses std::nth_element with greater<int>(), so the position holds the value that would be fourth if the list were sorted in descending order. It then prints the four largest values in any order.

It also shows the C++20 std::ranges versions. These take the container itself, not a pair of iterators. A ranges call looks a little shorter, and it does the same work.

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector<int> sales = {120, 45, 300, 88, 210, 150, 75, 300, 60, 190};
    int k = 4;
 
    vector<int> work = sales;
    nth_element(work.begin(), work.begin() + (k - 1), work.end(), greater<int>());
    cout << "4th largest: " << work[k - 1] << "\n";
    cout << "the 4 largest, in any order:";
    for (int i = 0; i < k; i++) cout << " " << work[i];
    cout << "\n";
 
    vector<int> top = sales;
    ranges::partial_sort(top, top.begin() + 3, greater<int>());
    cout << "ranges::partial_sort top 3:";
    for (int i = 0; i < 3; i++) cout << " " << top[i];
    cout << "\n";
 
    vector<int> nine = {5, 1, 9, 3, 7, 2, 8, 6, 4};
    ranges::nth_element(nine, nine.begin() + 4);
    cout << "ranges::nth_element median: " << nine[4] << "\n";
    return 0;
}

The output is:

4th largest: 190
the 4 largest, in any order: 210 300 300 190
ranges::partial_sort top 3: 300 300 210
ranges::nth_element median: 5

The sales list in descending order is 300, 300, 210, 190, 150, and so on. The fourth value is 190. The first four positions of work hold 210, 300, 300 and 190. Those four are the largest, and they are not sorted among themselves. The value 190 is correct at index 3, and that is all nth_element promises.

The median of the nine values 1 to 9 is 5, and the ranges version of nth_element gives the same answer. In this call, the comparator is left out, so the default < decides which values count as smaller.

What happens when the middle is the end

If the middle argument of partial_sort is the end of the range, every position is in the sorted front part. The call then does the same job as std::sort. The call below sorts the whole list in descending order.

vector<int> a = {72, 95, 61, 88, 90};
partial_sort(a.begin(), a.end(), a.end(), greater<int>());

The output of that call is:

partial_sort with middle at end: 95 90 88 72 61

The list is fully sorted, which is the same result sort gives. A call written this way is a sign that the author wanted a full sort, and std::sort says that more clearly.

Choosing between the tools

Use the table below to choose a tool. It lists the question you are answering and the call that answers it.

If k is close to n, a partial tool gains little. A full std::sort is simpler to read, and the speed difference is small. Pick a partial tool when k is much smaller than the list, or when you only need a single value.

Common mistakes

Reading the unsorted part as sorted. After partial_sort, only the front part is in order. After nth_element, only the chosen position is correct. The output of the examples above shows the leftover values in an arbitrary order, and that is correct. A program that depends on that order will sometimes pass and sometimes fail, depending on the data.

Passing an index where an iterator is needed. The median program needs an iterator for the position. Writing nth_element(v.begin(), v.size() / 2, v.end()) is a common error. The compiler rejects it with this message, shortened here to the first line:

mistake_compile.cpp:7:16: error: no matching function for call to ‘nth_element(std::vector<int>::iterator, std::vector<int>::size_type, std::vector<int>::iterator)’

The fix is to add the position to begin(), as the examples do: v.begin() + v.size() / 2.

Putting the middle past the end. The middle argument of partial_sort must lie inside the range, from the start up to the end. Asking for more positions than the list holds is a bug. A debug build catches it. With the -D_GLIBCXX_DEBUG flag, the program stops at the call and prints a message. This is the message for a list of four values and a middle six positions past the start:

Error: attempt to advance a dereferenceable (start-of-sequence) iterator 6 steps, which falls outside its valid range.

The message names the problem, which is a position that is too far from the start. Check the size of the list before you compute the middle.

Passing the end position as the chosen position of nth_element. The position must be an element of the list, and the end position is not one. In a debug build, the program in our test ran without any message and exited with code 0, so this bug can go unnoticed. Use a position from begin() up to, but not including, end().

Forgetting ties at the boundary. Suppose the fourth and fifth scores are both 17. A top-four call must choose one of them, and nothing in the call says which. If the comparator does not break the tie, the chosen value can change when the input order or the sort algorithm changes. Add a second key, as the records example does, if the choice matters.

Using a partial tool when you need every value in order. If the task needs the whole list sorted, use std::sort. A partial tool gives a weaker promise in that case, so the code is harder to read and gains nothing.

Practice

Exercise 1: The three smallest values, in order

Given the list 42, 7, 19, 88, 3, 56, 23, 11, 70, 5, use partial_sort to print the three smallest values in order.

Show the answer

vector<int> nums = {42, 7, 19, 88, 3, 56, 23, 11, 70, 5};
partial_sort(nums.begin(), nums.begin() + 3, nums.end());
cout << "3 smallest:";
for (int i = 0; i < 3; i++) cout << " " << nums[i];
cout << "\n";

The output is:

3 smallest: 3 5 7

The default comparator uses <, so the sorted front part is ascending.

Exercise 2: The median of an odd-sized list

Given the list 14, 2, 9, 30, 11, 25, 7, use nth_element to find the median. Use the middle position, which is index 3 for seven values.

Show the answer

vector<int> odd = {14, 2, 9, 30, 11, 25, 7};
nth_element(odd.begin(), odd.begin() + odd.size() / 2, odd.end());
cout << "median: " << odd[odd.size() / 2] << "\n";

The output is:

median: 11

Sorted, the list is 2, 7, 9, 11, 14, 25, 30. The fourth value is 11, which is the median. The call did not sort the list, and the other values are only split around 11.

Exercise 3: Explain why nth_element is not a sort

Look at the output of worked example 2. Explain in two or three sentences why it would be wrong to say that nth_element sorted the list.

Show the answer

The output shows the value 83 in the middle position, with the smaller values on its left and the larger values on its right. The values on each side are still in no particular order. For example, the left side starts with 67, then 55, which goes down before it goes up. A sorted list would have 55 first. So nth_element placed one value correctly and split the rest, and it did not sort the list.

Exercise 4: Top two, original kept

Given the scores 64, 91, 78, 85, copy the top two into a new list with partial_sort_copy. Print the copy and the original, and check that the original is unchanged.

Show the answer

vector<int> scores = {64, 91, 78, 85};
vector<int> best(2);
partial_sort_copy(scores.begin(), scores.end(), best.begin(), best.end(), greater<int>());
cout << "top 2 copy:";
for (int x : best) cout << " " << x;
cout << "\n";
cout << "original:";
for (int x : scores) cout << " " << x;
cout << "\n";

The output is:

top 2 copy: 91 85
original: 64 91 78 85

The copy has the two largest values in descending order. The original keeps its first order, because partial_sort_copy only reads it.

Exercise 5: Find the top five players

Using the Player records from worked example 4, write a program that prints the top five players. Use partial_sort, and explain what would change if you used nth_element instead to print the same five names.

Show the answer

Use partial_sort(players.begin(), players.begin() + 5, players.end(), better);, then print the first five entries in order. The top five are Ben, Dita, Emil, Gus and Asha. If you used nth_element with position 4 instead, the fifth player, Asha, would be correct, and the four players above Asha would be in the right group but in no particular order. To print the top five in order, partial_sort is the right tool, because it promises the front part is sorted.

Summary

• std::partial_sort sorts only the front part of a range. Use it for the top k values in order.
• std::nth_element places one chosen position correctly and splits the rest, but does not sort either side. Use it for medians and the k-th value.
• std::partial_sort_copy writes the sorted front part into a second list and leaves the original unchanged.
• Read the output of each call according to its promise. The leftover values are not sorted.
• Pass iterators, not index numbers, and keep every position inside the range. A debug build catches most of these mistakes.
• For nearly the whole list, use std::sort. Partial tools pay off only when the number you need is much smaller than the list.