Why this matters
Most real lists have many items with the same value for the field you sort by. A class list sorted by grade has ten students with grade B. A shop list sorted by price has three items at 499 rupees. If you sort only by grade, the ten B students come out in some arbitrary order. Often you want a second rule to decide the order among them, such as their roll number or their name. That second rule is what this lesson covers.
A sort that uses two or more fields is called a multi-key sort. The first field is the primary key, the main rule. The second field is the secondary key, which breaks ties in the primary key. You can have a third key, and so on. The idea is the same at every level.
This lesson uses only the sorting tools from the standard library, std::sort and std::stable_sort, and the comparison functions you can write yourself. It builds on the earlier lessons in this module. The heap sort lesson showed that heap sort is not stable, and that is the reason this lesson needs care. Later lessons in this module cover other sorts and the comparison rules that a sort depends on.
The idea in plain words
Imagine you have six staff members, each with a department, a name and a salary. You want them grouped by department, and inside each department sorted by name. Here is the list before sorting:
sales | Priya | 52000
it | Kiran | 61000
sales | Anand | 48000
it | Divya | 61000
hr | Sunil | 45000
it | Arjun | 70000The department is the primary key. The name is the secondary key. Sorting by department alone gives you three groups, but the names inside each group are in no particular order. Sorting by name alone gives you a list of names in order, but the departments are mixed up. Sorting by both gives you what you want: the departments in order, and inside each department, the names in order.
There are two common ways to do this in C++. The first uses two sorts in a row, and relies on a property called stability. The second uses one sort with a comparator that checks both keys. Both work. Each has a place where it is easier to read and easier to get right.
What stability means
A sort is stable when two items that compare as equal keep their original order. Suppose two items both have department it. If the sort is stable, the item that came first in the input still comes first in the output. If the sort is not stable, the two items may swap places.
The standard library gives you a stable version of the sort, called std::stable_sort. It has the same interface as std::sort. It takes the start and end iterators of a range and an optional comparator, and it reorders the range in place. Its extra promise is that equal items keep their order. It may allocate a temporary buffer about as large as the list.
The plain std::sort makes no such promise. For short lists, libstdc++, the standard library used by g++, often keeps equal items in order anyway. For longer lists it does not, so you should never rely on that behaviour.
Way 1: two stable sorts
The first method is a trick that uses stability. Sort by the secondary key first. Then sort by the primary key, using a stable sort. The second sort groups the items by primary key. Because it is stable, the items inside each group keep the order the first sort gave them. That order is the secondary key order.
The rule is simple to state: sort by the least important key first, and the most important key last. The first pass sets up the order that the later passes must not disturb.
Here is a program that does exactly this. It also prints the list after each step so you can see the effect.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Staff {
std::string dept;
std::string name;
int salary;
};
void show(const char* label, const std::vector<Staff>& rows) {
std::cout << label << '\n';
for (const Staff& s : rows) {
std::cout << " " << s.dept << " | " << s.name << " | " << s.salary << '\n';
}
}
int main() {
std::vector<Staff> rows = {
{"sales", "Priya", 52000},
{"it", "Kiran", 61000},
{"sales", "Anand", 48000},
{"it", "Divya", 61000},
{"hr", "Sunil", 45000},
{"it", "Arjun", 70000},
};
show("input", rows);
std::stable_sort(rows.begin(), rows.end(),
[](const Staff& a, const Staff& b) { return a.name < b.name; });
show("after pass 1 (by name)", rows);
std::stable_sort(rows.begin(), rows.end(),
[](const Staff& a, const Staff& b) { return a.dept < b.dept; });
show("after pass 2 (by dept, stable)", rows);
}Compile and run it:
g++ -std=c++20 -Wall two_pass.cpp -o two_pass
./two_passThe output is:
input
sales | Priya | 52000
it | Kiran | 61000
sales | Anand | 48000
it | Divya | 61000
hr | Sunil | 45000
it | Arjun | 70000
after pass 1 (by name)
sales | Anand | 48000
it | Arjun | 70000
it | Divya | 61000
it | Kiran | 61000
sales | Priya | 52000
hr | Sunil | 45000
after pass 2 (by dept, stable)
hr | Sunil | 45000
it | Arjun | 70000
it | Divya | 61000
it | Kiran | 61000
sales | Anand | 48000
sales | Priya | 52000The second block is the list sorted by name. Anand comes first, then Arjun, Divya, Kiran, Priya and Sunil. The department is mixed up, which is expected at this stage.
The third block is the result after the stable sort by department. The hr group has only Sunil. The it group comes next, and it is in name order: Arjun, Divya, Kiran. The sales group is last, with Anand before Priya. The names inside each group are in order, because the stable sort kept the name order from pass 1. Without stability, the it group could come out in any order.
Reading the two-pass code
Each std::stable_sort call reads like one step in a recipe. The first call says "put the list in name order." The second call says "group by department, and keep the name order inside each group." The comparator in each call only looks at one key, which keeps each line easy to check.
The cost is that you run the sort once per key. With two keys, that is two passes over the list. With three keys, it is three. Each pass takes O(n log n) time, so the total is still O(k n log n) for k keys. For the small lists in this lesson, the cost does not matter. For a list with millions of rows, you might prefer the one-comparator method, which does a single pass.
Way 2: one comparator with std::tie
The second method uses one sort and a comparator that looks at both keys. The comparator must follow a simple rule: if the primary keys differ, the answer comes from the primary keys. If they are equal, the answer comes from the secondary keys.
You could write that rule with two if statements. The C++ standard library gives you a shorter way, using a tuple. A tuple is a fixed group of values, written with std::tuple in the <tuple> header. Tuples compare one element at a time, from left to right. So std::make_tuple(x1, y1) < std::make_tuple(x2, y2) checks x1 against x2 first, and only checks y1 against y2 when x1 and x2 are equal.
The helper std::tie builds a tuple of references to existing values. A reference is a second name for the same value, so comparing a tuple of references compares the original fields without copying them. Here is the comparator:
std::sort(rows.begin(), rows.end(), [](const Staff& a, const Staff& b) {
return std::tie(a.dept, a.name) < std::tie(b.dept, b.name);
});Read it as: a comes before b when the dept of a is before the dept of b, or the depts are equal and the name of a is before the name of b. That is exactly the rule we want.
Here is the full program. It sorts the same six rows with one call and prints the result.
#include <algorithm>
#include <iostream>
#include <string>
#include <tuple>
#include <vector>
struct Staff {
std::string dept;
std::string name;
int salary;
};
void show(const char* label, const std::vector<Staff>& rows) {
std::cout << label << '\n';
for (const Staff& s : rows) {
std::cout << " " << s.dept << " | " << s.name << " | " << s.salary << '\n';
}
}
int main() {
std::vector<Staff> rows = {
{"sales", "Priya", 52000},
{"it", "Kiran", 61000},
{"sales", "Anand", 48000},
{"it", "Divya", 61000},
{"hr", "Sunil", 45000},
{"it", "Arjun", 70000},
};
std::sort(rows.begin(), rows.end(), [](const Staff& a, const Staff& b) {
return std::tie(a.dept, a.name) < std::tie(b.dept, b.name);
});
show("one comparator (dept, then name)", rows);
}The output is:
one comparator (dept, then name)
hr | Sunil | 45000
it | Arjun | 70000
it | Divya | 61000
it | Kiran | 61000
sales | Anand | 48000
sales | Priya | 52000This is the same result as the two-pass method. The tuple comparison did the work of both passes at once. Because the comparator decides the order of every pair completely, the result does not depend on the starting order of the list, and it does not need stability.
Why std::tie and not a plain tuple
You can also write std::make_tuple(a.dept, a.name). That works, but it copies the strings into a new tuple each time the comparator runs. The sort calls the comparator many times, so the copies add up. std::tie avoids the copies. It does not change the result.
One limit is worth knowing now. A tuple comparison always sorts every key in the same direction, from small to large. It cannot sort one key from high to low and another from low to high. For that, you need the comparator to be written by hand, as the next section shows.
Example 2: three keys with mixed directions
Real rules often mix directions. A typical rule is: department from A to Z, then salary from high to low, then name from A to Z. The salary goes in the opposite direction from the other two keys.
The clearest way to write this is a comparator with one if for each key. Each if checks whether the two items differ on that key. If they do, it returns the answer. If they do not, it moves on to the next key. The last line decides the rest.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <string>
#include <vector>
struct Staff {
std::string dept;
std::string name;
int salary;
};
void show(const char* label, const std::vector<Staff>& rows) {
std::cout << label << '\n';
for (const Staff& s : rows) {
std::cout << " " << s.dept << " | " << s.name << " | " << s.salary << '\n';
}
}
int main() {
std::vector<Staff> rows = {
{"sales", "Priya", 52000},
{"it", "Kiran", 61000},
{"sales", "Anand", 48000},
{"it", "Divya", 61000},
{"hr", "Sunil", 45000},
{"it", "Arjun", 70000},
};
std::vector<Staff> by_comparator = rows;
std::sort(by_comparator.begin(), by_comparator.end(),
[](const Staff& a, const Staff& b) {
if (a.dept != b.dept) return a.dept < b.dept;
if (a.salary != b.salary) return a.salary > b.salary;
return a.name < b.name;
});
show("comparator: dept, salary high to low, name", by_comparator);
std::vector<Staff> by_passes = rows;
std::stable_sort(by_passes.begin(), by_passes.end(),
[](const Staff& a, const Staff& b) { return a.name < b.name; });
std::stable_sort(by_passes.begin(), by_passes.end(),
[](const Staff& a, const Staff& b) { return a.salary > b.salary; });
std::stable_sort(by_passes.begin(), by_passes.end(),
[](const Staff& a, const Staff& b) { return a.dept < b.dept; });
show("three stable passes: name, then salary, then dept", by_passes);
bool same = by_comparator.size() == by_passes.size();
for (std::size_t i = 0; same && i < by_comparator.size(); ++i) {
same = by_comparator[i].name == by_passes[i].name;
}
std::cout << "same order: " << same << '\n';
}The output is:
comparator: dept, salary high to low, name
hr | Sunil | 45000
it | Arjun | 70000
it | Divya | 61000
it | Kiran | 61000
sales | Priya | 52000
sales | Anand | 48000
three stable passes: name, then salary, then dept
hr | Sunil | 45000
it | Arjun | 70000
it | Divya | 61000
it | Kiran | 61000
sales | Priya | 52000
sales | Anand | 48000
same order: 1Check the output against the rules. Within it, Arjun has the highest salary, 70000, so he comes first. Divya and Kiran both earn 61000, so the name rule decides, and Divya comes before Kiran. Within sales, Priya earns 52000 and Anand earns 48000, so Priya comes first, even though Anand comes before Priya alphabetically. The salary rule beats the name rule because it is the more important key.
The second block gives the same order with three stable passes. The passes run in the reverse order of the rules: name first, then salary, then department. The last pass is the most important key, and it is the one that groups the rows. The earlier passes survive inside each group because the sorts are stable.
Notice how each key is written. The comparator needs a line for every key, and each line must handle one direction. The passes need one line per key, and the direction is set by the comparison: < for ascending, > for descending. Both forms are correct. The comparator is the better choice when the rules are complicated, because all the logic sits in one place. The passes are the better choice when you want each rule to be a separate, named step, and when you can reuse the same sort for a different order.
Example 3: sorting words by length and then by letters
Here is a smaller example with plain strings, to show the pattern without the struct. The rule is: shorter words first, and among words of the same length, alphabetical order. A std::tie line does not fit here, because a.size() returns a new number and std::tie needs existing values. So the comparator checks the length first, with an if, and then the letters.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
int main() {
std::vector<std::string> words = {
"mango", "fig", "apple", "kiwi", "pear", "plum", "date", "lime",
};
std::sort(words.begin(), words.end(), [](const std::string& a, const std::string& b) {
if (a.size() != b.size()) return a.size() < b.size();
return a < b;
});
for (const std::string& w : words) std::cout << w << ' ';
std::cout << '\n';
}The output is:
fig date kiwi lime pear plum apple mango The comparator puts the length first. Words of length 3 come first: fig. Then the words of length 4 are in alphabetical order: date, kiwi, lime, pear, plum. The words of length 5 come last: apple and mango. Putting return a < b; first would make the length check never run, so the order would be plain alphabetical.
Common mistakes
Running the passes in the wrong order
The most common mistake with two stable sorts is to run them in the wrong order. If you sort by the primary key first and the secondary key last, the second pass undoes the first. The second sort is stable, so it keeps the order of equal items. It is also the sort that decides the order between different items, and it uses only the secondary key. The result is a list sorted by the secondary key alone.
Here is a program with the passes swapped. It uses the same six rows as before.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Staff {
std::string dept;
std::string name;
int salary;
};
int main() {
std::vector<Staff> rows = {
{"sales", "Priya", 52000},
{"it", "Kiran", 61000},
{"sales", "Anand", 48000},
{"it", "Divya", 61000},
{"hr", "Sunil", 45000},
{"it", "Arjun", 70000},
};
std::stable_sort(rows.begin(), rows.end(),
[](const Staff& a, const Staff& b) { return a.dept < b.dept; });
std::stable_sort(rows.begin(), rows.end(),
[](const Staff& a, const Staff& b) { return a.name < b.name; });
for (const Staff& s : rows) {
std::cout << s.dept << " | " << s.name << " | " << s.salary << '\n';
}
}The output is:
sales | Anand | 48000
it | Arjun | 70000
it | Divya | 61000
it | Kiran | 61000
sales | Priya | 52000
hr | Sunil | 45000The list is in name order. The departments are not grouped at all. Sales, it and hr appear in a mixed order, because the last sort used only the name. The fix is to swap the two calls, so that the name pass runs first and the department pass runs last.
Using std::sort for the passes
The second mistake is to use the plain std::sort for the passes, not std::stable_sort. The two-pass method depends on stability, and std::sort does not promise it. The program below does the two passes with std::sort, on a list of 40 rows. The rows have three departments, and the names are chosen by a simple number generator, so they are in no particular order. After the two passes, the program counts how many pairs inside a department are out of name order.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <string>
#include <vector>
struct Staff {
std::string dept;
std::string name;
int salary;
};
int count_bad(const std::vector<Staff>& rows) {
int bad = 0;
for (std::size_t i = 1; i < rows.size(); ++i) {
if (rows[i - 1].dept == rows[i].dept && rows[i - 1].name > rows[i].name) ++bad;
}
return bad;
}
int main() {
std::vector<Staff> big;
unsigned seed = 7;
for (int i = 0; i < 40; ++i) {
seed = seed * 1103515245u + 12345u;
int name_no = static_cast<int>((seed >> 16) % 40);
big.push_back({"d" + std::to_string(i % 3), "n" + std::to_string(100 + name_no), 0});
}
std::vector<Staff> unstable = big;
std::sort(unstable.begin(), unstable.end(),
[](const Staff& a, const Staff& b) { return a.name < b.name; });
std::sort(unstable.begin(), unstable.end(),
[](const Staff& a, const Staff& b) { return a.dept < b.dept; });
std::cout << "two std::sort calls, 40 rows: names out of order inside a dept = "
<< count_bad(unstable) << '\n';
std::vector<Staff> stable = big;
std::stable_sort(stable.begin(), stable.end(),
[](const Staff& a, const Staff& b) { return a.name < b.name; });
std::stable_sort(stable.begin(), stable.end(),
[](const Staff& a, const Staff& b) { return a.dept < b.dept; });
std::cout << "two stable_sort calls, 40 rows: names out of order inside a dept = "
<< count_bad(stable) << '\n';
}The output is:
two std::sort calls, 40 rows: names out of order inside a dept = 17
two stable_sort calls, 40 rows: names out of order inside a dept = 0The plain sort left 17 pairs out of order, so the name order was lost inside the departments. The stable sort left none. The lesson is that the two-pass method needs std::stable_sort in every pass after the first. If you need a stable result, you can also use a single comparator, which does not depend on stability at all.
A short list can hide the problem. For short lists, libstdc++ uses insertion sort, which is stable, so the same two calls may look correct on six rows. Test with a list large enough to matter before you trust a sort.
Forgetting the type has no less-than
The third mistake shows up when you sort a vector of structs without giving a comparator. The default comparator is <. A struct has no < unless you write one, so the compiler stops. Here is a program that makes this mistake:
#include <algorithm>
#include <string>
#include <vector>
struct Staff {
std::string dept;
std::string name;
};
int main() {
std::vector<Staff> rows = {{"it", "Kiran"}, {"hr", "Sunil"}};
std::sort(rows.begin(), rows.end());
}Compiling it with g++ 15.2.0 prints a long error. The first error line, shortened, is:
predefined_ops.h:45:23: error: no match for 'operator<' (operand types are 'Staff' and 'Staff')The message is long because the compiler prints the path through the standard library where it tried to use <. The phrase to look for is no match for 'operator<', followed by the struct name. The fix is to pass a comparator as the third argument of std::sort, as the examples in this lesson do.
Writing the comparator with || and &&
The fourth mistake is to write a comparator with || and && in a way that does not follow the rule. For example, return a.dept < b.dept || a.name < b.name; looks close to the right answer, but it is not a valid comparator. Take the rows (it, Kiran) and (hr, Sunil). The comparator returns true when the first row is a, because Kiran comes before Sunil. It also returns true when the second row is a, because hr comes before it. A comparator must never say that each of two items comes before the other, and std::sort can then give a wrong order or read outside the list. The safe forms are the if chain and the std::tie tuple, which the examples above use. The lesson on bad comparator bugs explains why this matters and how to test a comparator.
Sorting by a key that is not the one you meant
The fifth mistake is simple but easy to miss. Inside a comparator, the key on the left side must come from a, and the key on the right side must come from b. A line like return a.dept < a.name; compiles, because both values are strings, and it gives an answer that makes no sense. Check each comparator by reading its two sides. The left side should use the same key as the right side, from the other object.
Practice
Exercise 1: two passes by hand
You have the list (dept, name) pairs: (b, z), (a, y), (b, x), (a, z). Sort by name, then by dept, using two stable passes. Write the list after each pass.
Show the answer
Sort by name first, A to Z: (b, x), (a, y), (b, z), (a, z). The two z items keep their order: (b, z) came before (a, z) in the input. Sort by dept next, stably: the a items come first, in the order they had: (a, y), then (a, z). Then the b items, in their order: (b, x), then (b, z). The final list is (a, y), (a, z), (b, x), (b, z).
Exercise 2: a comparator for two keys
Write a comparator that sorts the Staff rows by salary from low to high, and by name from A to Z when two salaries are equal. Use the rows from this lesson. Write the expected output.
Show the answer
The comparator is:
[](const Staff& a, const Staff& b) {
if (a.salary != b.salary) return a.salary < b.salary;
return a.name < b.name;
}The rows in order are: Sunil 45000, Anand 48000, Priya 52000, Divya 61000, Kiran 61000, Arjun 70000. Divya and Kiran have the same salary, and Divya comes first because D is before K. The department column is not used in this sort, so the rows from different departments mix freely.
Exercise 3: why the passes need stability
A student uses std::sort for the second pass of a two-pass sort. Explain in your own words what could go wrong. Then say which function to use instead, and why the first pass is not enough on its own.
Show the answer
The second pass sorts by the primary key. If std::sort is used, it can move items that have the same primary key, so the order from the first pass inside each group can be lost. The result is grouped by the primary key, but the secondary order is not reliable. The fix is std::stable_sort, which keeps equal items in their order from the previous pass. The first pass is not enough on its own, because it only sets the order of the secondary key. It has no effect on the grouping, which only the second pass creates.
Exercise 4: sort words by length, longest first
Write a comparator for the words in Example 3 that puts the longest words first. For words of the same length, use alphabetical order. Write the output for the words "mango", "fig", "apple", "kiwi", "pear", "plum", "date" and "lime".
Show the answer
The comparator is:
[](const std::string& a, const std::string& b) {
if (a.size() != b.size()) return a.size() > b.size();
return a < b;
}The output is apple mango date kiwi lime pear plum fig. The words of length 5 come first: apple, then mango, because apple is before mango alphabetically. Then the words of length 4 in alphabetical order: date, kiwi, lime, pear, plum. The word of length 3, fig, comes last.
Exercise 5: ties on every key
Take the three-key comparator from Example 2 and the three stable passes. Suppose two rows are equal on dept, salary and name, such as two identical copies of (it, Divya, 61000). Which method keeps those two rows in their input order, and why?
Show the answer
The stable passes keep them in their input order, because each std::stable_sort keeps equal items in order. The comparator method uses std::sort, which does not promise that. The comparator returns false both ways for two equal rows, so the sort may swap them. If the two copies are identical, the swap does not show. If they differ in a field the comparator does not read, such as a row id, the swap can change the output. When the full key may repeat, use the stable passes, or add the missing field to the comparator as a last key.
Summary
- A multi-key sort uses a primary key for the main order and a secondary key for ties.
- Two stable sorts work when you sort by the least important key first and the most important key last.
- One comparator works when it checks each key in turn and returns the answer for the first key that differs.
std::tiemakes a short comparator for ascending keys, but it cannot mix directions, so write a comparator by hand for that.- Use
std::stable_sortfor the passes, becausestd::sortdoes not keep equal items in order. - Check every comparator by reading its two sides, and test with a list large enough to show any mistake.