std::sort and comparators

Why it matters

In real work, and in most contests, you rarely write your own sort. You call the standard library, which is written by experts, tested for years, and faster than most hand-written versions. The skill that matters is telling the library how to order your data. A sort is only as correct as the rule you give it. The second skill is choosing between a sort that may reorder ties and one that keeps them in their original order.

This lesson is about that skill. You will see how std::sort takes a range, how a comparator decides the order, how lambdas let you write small rules where you use them, and how std::stable_sort keeps ties in place. You will also see the comparator mistake that makes a program crash in the middle of a sort, and what that crash looks like.

Ranges: where the sort starts and stops

std::sort lives in the header <algorithm>. You must include it. Every call to the sort gives it a range, which is a start and an end. The start is the first value to sort. The end is one position past the last value. This "one past the end" rule appears throughout the C++ library, so get used to it now.

For a vector, the range is v.begin() to v.end(). The functions begin and end return iterators. An iterator is an object that points to a position in a container, the same way an index does. You can think of v.begin() as "index 0" and v.end() as "index size()". The sort works on every position from the start up to, but not including, the end.

sort(v.begin(), v.end());

For a plain array, the iterators are ordinary pointers. The array name is the start, and the name plus the count is the end. For an array of four values, the call is sort(arr, arr + 4). The expression arr + 4 points to the position after the last value, just like v.end().

The default order is ascending, from smallest to largest. The sort runs in O(n log n) time on average and in the worst case, using a method that combines quick sort with other methods. It is not stable, which means equal values may swap places. Keep that fact in mind, because the stable version comes later in this lesson.

Running the basics

The first program sorts a vector ascending, then descending, then an array, and then only part of an array. It needs no input.

Expected output:

1 2 5 6 9
9 6 5 2 1
10 20 30 40
7 8 9 6 5 4

The descending sort uses greater<int>() from the header <functional>. It is a small function object that answers "is the first value bigger than the second?", and passing it as the third argument reverses the order. The last sort covers only the first three values of nums, which are 9, 8 and 7. Its end is nums + 3, so the values 6, 5 and 4 never move.

Comparators: deciding what comes first

Every call to sort uses a rule to decide the order. The rule is called a comparator. It is a function that takes two values and returns true when the first value should come before the second. The default comparator for numbers is <. When you give the sort a third argument, you replace that rule.

For your own data, you usually write the rule as a lambda. A lambda is a function written inline, right where it is used, with no name. Its form is a square bracket, then a parameter list, then a body in braces.

[](const Student& a, const Student& b) { return a.marks > b.marks; }

The square brackets are the capture list. It is empty here, which means the lambda uses no variables from outside. The parentheses hold the parameters. The two parameters are references to the values being compared. The const says the lambda only reads them, and the & says it uses the original values, not copies. The body returns a bool, which says whether a comes before b.

Lambdas are the normal way to write comparators in modern C++. A named function works too, but the lambda keeps the rule next to the sort, so a reader sees both at once.

A record with a two-part rule

Real data has more than one field. A student has a name and marks. A common rule is to sort by marks from highest to lowest, and to break ties by name from A to Z. The rule has two parts. The second part only matters when the first part ties.

The program below reads a count and then name marks pairs, and prints the leaderboard. Type these lines into the Input box:

5
Priya 72
Arjun 91
Bina 85
Zoya 72
Chirag 91

Expected output:

Arjun 91
Chirag 91
Bina 85
Priya 72
Zoya 72

Walk through the comparator on two students with the same marks, Priya and Zoya. The first test, a.marks != b.marks, is false, because both have 72. So the function goes on to the second line and returns a.name < b.name. Priya is less than Zoya in alphabetical order, so Priya comes first. On two students with different marks, the first test is true, and the function returns a.marks > b.marks, which puts the bigger mark first.

The two-part pattern is one of the most common comparator shapes in interviews and in work. Write the most important key first. If the values are equal, return the next key. Stop when there are no more keys.

Pairs compare for free

C++ also knows how to order a pair. A pair compares its first value, then its second value if the firsts are equal. So sort on a vector of pairs gives a two-key sort with no lambda at all. This also works for tuple, which holds three or more values. A pair is the right tool when the two keys are plain numbers in the natural order. A lambda is needed when you want one key descending and the other ascending, or when the keys are text with a special rule.

Stability: keeping ties in order

Lesson 2 defined a stable sort. A stable sort keeps items that compare as equal in their original order. std::sort does not promise that. The standard library provides std::stable_sort for exactly this purpose. It has the same kind of call, and it keeps ties in their input order.

Use stable_sort whenever the input order carries meaning that the sort must keep. Examples include a queue that must stay first-come, first-served, or a list that was already sorted by a secondary key. The cost is a little more memory and sometimes a little more time.

The program below sorts a list of words by length, shortest first. Words of the same length must stay in the order they were typed. Type these lines into the Input box:

6
kiwi fig apple pear plum date

Expected output:

fig kiwi pear plum date apple

The four-letter words kiwi, pear, plum and date keep their input order. kiwi was first, so it comes first among the four-letter words. fig is the only three-letter word and comes first overall. apple is the only five-letter word and comes last. If you replace stable_sort with sort, the four-letter words may come out in a different order. The output would still be sorted by length, but the tie order would not be guaranteed.

Captures and distance rules

Sometimes a rule needs a value from outside the lambda. A distance rule might sort points by how far they are from a fixed point, or a number line might be sorted by how far each value is from a target. The capture list brings outside values into the lambda. A capture like [target] copies the variable target into the lambda, so the body can use it.

The next program sorts numbers by how close each is to a target, with ties broken by value. Type these lines into the Input box. The first line holds the count and the target, and the second line holds the numbers:

5 10
12 3 9 15 8

Expected output:

9 8 12 15 3

The distances from 10 are 2 for 12, 7 for 3, 1 for 9, 5 for 15 and 2 for 8. So 9 comes first, then 8 and 12 tie at distance 2, and the tie goes to the smaller value, 8. Then 12 comes, then 15 and 3. The lambda uses abs from <cstdlib> to get the distance. The capture [target] gives it access to the target, and the parameters int x and int y are values rather than references, which is fine for ints.

The program above sorts the values themselves. Sometimes you need to know where each value came from. In that case, sort the positions instead of the values. The next program does this. It sorts the indexes 0 to n minus 1 by the score at each index, and then uses the sorted indexes to compute the rank of each student in the original order.

Type these lines into the Input box:

5
70 90 65 55 88

Expected output:

student 1 score 70 rank 3
student 2 score 90 rank 1
student 3 score 65 rank 4
student 4 score 55 rank 5
student 5 score 88 rank 2

The function iota from <numeric> fills the array of positions with 0, 1, 2 and so on. The comparator reads score[i] and score[j] through the captured reference &score, so it compares scores while sorting positions. After the sort, order[0] is the position of the highest score. The loop that follows writes rank r + 1 into the slot for that position. This pattern is called argsort, short for argument sort. It is useful whenever you need to sort one list while keeping track of another list.

Rules a comparator must follow

A comparator is a promise. It must answer "should a come before b?" in a way that is consistent for every pair of values. The C++ standard calls this a strict weak ordering. You do not need the formal name, but you need its two plain rules.

1. A value is never before itself. For the same value, the comparator returns false.
2. If a comes before b, then b does not come before a.

The most common way to break these rules is to use >= or <= instead of > or <. With >=, two equal values each say that the other should come first, because each is greater than or equal to the other. The sort relies on the promise, so the result can be wrong, and the program can crash in the middle of the sort.

The program below uses the broken comparator on a vector of 40 values, where 39 are 7 and one is 3. The output is not the point. Read the crash message.

vector<int> v(40, 7);
v[20] = 3;
sort(v.begin(), v.end(), [](int a, int b) { return a >= b; });

On the g++ compiler used for this lesson, the program stops with this message and exit code 134.

double free or corruption (out)

That message means the sort wrote outside the memory it owns, because its search assumed the comparator was consistent. The same comparator on the small array 3 1 2 happens to print 3 2 1, which is why this bug is easy to miss. A test with only a few distinct values can pass, and the same code crashes when a real data set has many equal values. The fix is to use > in the comparator.

Two smaller rules follow from the same promise. Do not change the data inside a comparator, because the sort may call it many times on the same pair. And pass records by const&, so the comparator reads them without copying, which keeps the sort fast when the records are large.

Defining the order inside the struct

A comparator is not the only way to give a struct an order. You can define the less-than operator for the struct itself. Then sort with no third argument uses your operator. This is useful when a type has one natural order that every part of the program should share, such as a date or a version number.

struct Student {
    string name;
    int marks;
 
    bool operator<(const Student& other) const {
        if (marks != other.marks) return marks > other.marks;
        return name < other.name;
    }
};

With this operator, sort(s.begin(), s.end()); gives the leaderboard order from the earlier example. The operator is a member function. The word const at the end says that it does not change the student it is called on. The parameter other is the student on the right-hand side of the comparison.

The choice is between one fixed order and one order per call. An operator fixes the order for every use of the type. A lambda lets each call sort differently. If the order is part of what the type means, the operator is the better choice, and it has an extra benefit: the standard containers std::set and std::map order their items with < by default, so they will use your rule too. If the order is a one-off report, a lambda at the call site is clearer.

The risk with an operator is surprise. Someone who sorts the same students by name, in another part of the program, gets the marks order unless they check the operator first. Put a comment next to the operator that states the rule in words, so the next reader does not have to work it out.

A three-key rule, worked by hand

Suppose a shop keeps a stock list and wants it sorted by three keys. The first key is the category, from A to Z. The second key is the price, from highest to lowest. The third key is the item name, from A to Z. The comparator must check the keys in that order, and move to the next key only when the current one ties.

struct Item {
    string category;
    int price;
    string name;
};
 
sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
    if (a.category != b.category) return a.category < b.category;
    if (a.price != b.price) return a.price > b.price;
    return a.name < b.name;
});

Trace this rule on four items, given in this input order: rice in food at 50, tea in drink at 20, oil in food at 80, and bread in food at 50.

1. Compare by category first. Drink comes before food, so tea moves to the front of the list.
2. Among the food items, compare by price, highest first. Oil at 80 comes before the two items at 50. Rice and bread tie at 50.
3. Rice and bread tie on price, so compare by name. Bread comes before rice.

The final order is tea (drink, 20), oil (food, 80), bread (food, 50), rice (food, 50). Notice how each if only matters when the one before it returned false. The second line can only decide the order of two items in the same category. The third line can only decide the order of two items with the same category and price.

This pattern works for any number of keys, and it is easy to check. Write one if per key, in order of importance, and end with the least important key as a plain return. For ascending numbers only, you can also compare a tuple, such as make_tuple(a.category, a.name) < make_tuple(b.category, b.name). A tuple compares its items in order, like a pair. Negating a number turns a descending key into an ascending one, which works for numbers but not for text.

What happens inside

It helps to know what the sort does with your comparator. std::sort in the C++ standard library is an introsort. It starts with a quick sort, as lesson 3 described. It chooses pivots by a median rule, which avoids the worst case on sorted input. If the recursion gets too deep, it switches to heap sort, which guarantees n log n time. For small pieces of a dozen values or fewer, it switches to insertion sort, which lesson 1 showed is fast on small inputs.

Your comparator is called many times, roughly n log n times. Each call is a function call that reads two values and returns a bool. The lambda's capture list decides what it reads. A lambda with no captures is just a small function, and the compiler often inlines it, which means the call costs almost nothing.

The sort moves your values, not the comparator. It swaps or copies records within the range, so for a vector of large records, the moves are the expensive part. This is why sorting a vector of pointers or indexes can be faster than sorting the records. The argsort program above moves only integers, while the comparator reads the scores through a reference.

The iterators are the bridge between the sort and the container. A vector's iterators point into one contiguous block of memory, so the sort can index into it quickly. A list's iterators point to separate nodes, so std::sort does not work on a list. The standard library has a list::sort member function for that case, which uses a merge sort on the nodes.

Common mistakes

The compiler and the runtime both catch some mistakes, so each one below comes with what you will see.

Forgetting the header

If you write sort without #include <algorithm>, the compiler stops with this message. The example uses <iostream> and <vector> only.

err1.cpp:7:5: error: ‘sort’ was not declared in this scope; did you mean ‘short’?

The compiler does not know the name sort, so it guesses a similar name. Add #include <algorithm> at the top, and the message goes away. Read the first error line, not the whole screen. It gives the file, the line and the reason.

Sorting a struct without a rule

If you call sort on a vector of records but give no comparator, the sort uses < on each record. A struct has no < unless you write one, so the compiler reports an error deep in the library code. The first useful line is this one.

/usr/include/c++/15/bits/predefined_ops.h:45:23: error: no match for ‘operator<’ (operand types are ‘Student’ and ‘Student’)

The message names the type, Student, and the missing operator. Fix it by passing a comparator as the third argument, which is what the earlier examples do.

A missing parenthesis on a comparator object

Writing greater<int> without the parentheses passes the template, not an object. The compiler then reports a problem with a parenthesis.

err3.cpp:9:42: error: expected primary-expression before ‘)’ token

The fix is greater<int>(), with the empty parentheses that make it an object. The column number in the message points at the spot where the compiler gave up.

The end that is one too early

The call sort(v.begin(), v.end() - 1) compiles and runs without any error message. It sorts every value except the last one, which stays where it is. The output looks almost right, and the bug is easy to miss. When an answer is missing its last value, check the end of the range.

Equal keys with sort

When the output of sort must keep the input order for equal keys, sort is the wrong tool. A test that passes on your computer may fail on another compiler, because the order of ties is not promised. Use stable_sort, and check the tie order in a test.

Using >= in a comparator

This is the crash described above. The fix is > or <, and the test that catches it is one with many equal values.

Changing data inside the comparator

A comparator should only read its two inputs. If it changes a value, the same pair can get a different answer on the next call, which breaks the promise the sort depends on. The sort may then skip values, compare the same value twice, or leave the array partly sorted. Keep comparators pure: the same two inputs must always give the same answer, and nothing else may change.

Comparing floating-point keys for ties

With double keys, two values that should tie may differ by a tiny rounding error. For example, 0.1 + 0.2 is not exactly equal to 0.3 in binary floating point. A tie test such as a.price != b.price then never fires for those values, and the order can look random. Store money in whole units, such as cents, or compare with a small tolerance.

Debugging walkthrough

Here is a session on a leaderboard that puts the wrong students at the top. The comparator is written as if (a.marks != b.marks) return a.marks > b.marks; return a.name > b.name;, which sorts names from Z to A instead of A to Z.

1. Find a small input where the wrong order shows. Two students with the same marks are enough. Print both names, in the order the program gives.
2. Write the comparator on paper for that pair. For Priya 72 and Zoya 72, the first test is false, so the second test decides. With > in the name test, Zoya comes first, which is wrong.
3. Fix the second test to a.name < b.name. Run the same input again.
4. Test an input with no equal marks, to confirm the first test still works.
5. Test a larger input with many equal marks, to confirm the rule is strict and the program does not crash.

When a sort gives a wrong order, the comparator is almost always the cause. Print the two values in the comparator for one failing pair. The problem is usually visible in the output of that single call.

Choosing the right call

When you sit down to sort something, ask four questions in order. The answers pick the call for you.

1. Do you need every value in order, or only the first few? If only the top k, use partial_sort. If only the k-th value, use nth_element. A full sort is the most work, so use it only when you need the whole order.
2. Do equal items need to keep their input order? If yes, use stable_sort. If no, sort is faster and uses less memory.
3. Is the order a rule for the type everywhere, or a rule for one report? A type-wide rule belongs in operator<. A one-off rule belongs in a lambda at the call site.
4. Are the keys plain numbers, or do they have a rule? Plain numbers in their natural order can use the default comparison. Anything else needs a comparator that checks each key in turn.

A quick way to check your choice is to test it on a list with duplicates and with one item. Duplicates test the tie rule, and one item tests the edge case of the range. If both pass, the call is almost certainly right.

Variations and edge cases

• Empty range. sort(v.begin(), v.end()) on an empty vector does nothing and is safe. So is sort(arr, arr) on an empty array.
• Sorting strings. Strings compare letter by letter with <. Uppercase letters come before lowercase letters, because their character codes are smaller. If you want case-insensitive order, write a lambda that converts both strings to lower case first.
• Partial sort. partial_sort sorts only the first k values and leaves the rest in an unspecified order. It is useful for finding the top ten of a long list. nth_element puts the k-th value in its place and divides the rest around it, which is quickselect from lesson 3.
• Descending for pairs. A pair compares ascending by default. To sort pairs by the first value descending and the second ascending, use a lambda with two tests, as in the leaderboard example.
• Sorting by several keys with two passes. Lesson 2 showed that stable sorts can handle several keys. The same idea works with stable_sort, which is often easier to read than one long comparator.
• Floating-point values. sort works on doubles. Be careful with NaN, because it breaks the strict weak ordering. Remove or handle NaN before sorting.

Interview patterns and questions

Interviewers expect you to choose the right tool and to explain the cost. These are common questions.

1. "Sort intervals by their start time." Sort a vector of pairs, or a struct with a comparator on the start. The sort costs O(n log n). Many interval problems, such as merging overlapping meetings, start with this step.
2. "Find the top k items." Use partial_sort for O(n log k), or nth_element for O(n) average time when the order of the top k does not matter. Mention both, and explain why a full sort is more work than needed.
3. "Sort objects by a rule that changes at runtime." Pass a lambda that captures the rule variable, as the distance example does.
4. "Why is the sort not stable, and what do you use instead?" The fast algorithm moves values past equal ones. Use stable_sort, which costs more memory.
5. "Sort people by age, then by name." A pair of age and name in a vector, or a lambda with two tests. Say why the first test must be the most important key.
6. "What breaks if your comparator uses <=?" Equal values each claim to come first, which breaks the promise the sort depends on. The result may be wrong, or the program may crash.

The pattern behind most of these answers is this. Name the keys in order of importance. Write one test per key. Use a stable sort if an earlier order must survive. Say the cost, which is O(n log n) for a full sort and less for a partial one.

Sort, then scan: merging intervals

Many interview questions about time ranges use one pattern. Sort the ranges by their start time, then walk the list once and merge each range into the last one when they overlap. The sort does the ordering work, and the scan does the merging. Lesson 3 showed merging two sorted piles. Here the sort gives you the sorted list for free.

sort(meetings.begin(), meetings.end());   // pairs sort by start, then by end
vector<pair<int, int>> merged;
for (auto& m : meetings) {
    if (!merged.empty() && m.first <= merged.back().second) {
        merged.back().second = max(merged.back().second, m.second);
    } else {
        merged.push_back(m);
    }
}

The sort costs O(n log n). The scan visits each meeting once, so it costs O(n). The whole method is O(n log n), and the extra memory is the output list. Interviewers often ask what changes if the list is already sorted. The sort then takes about O(n) time with a good algorithm, but the scan is the same. This is the method behind the Merge Meetings problem in this module's coding set, where touching meetings count as overlapping, which is why the test uses <=.

Real-world uses

Every program that shows a ranked list uses a comparator. A search engine ranks results by relevance, then by date for ties. A shop lists products by price, then by name. A bank sorts transactions by time, then by id, so the same statement is produced every time.

Argsort is common in data work. A spreadsheet sorts one column and drags the other columns along. The same idea lets a program sort a table of records while keeping a separate array of positions for fast lookups.

Stable sorts matter where the order of a list is a promise to a user. A ticket queue must stay in arrival order among tickets with the same priority. A stable sort gives that order without extra code.

Practice

Try these in order. Write your own answer first, then check the hidden solution.

1. Sort by last digit. Read n numbers and print them sorted by their last digit, keeping the input order for ties. Hint: compare a % 10 and b % 10, and use stable_sort.

2. Shortest word first, then alphabetical. Sort words by length, shortest first. Among words of the same length, sort alphabetically. Hint: use two tests in the lambda, as the leaderboard does.

sort(words.begin(), words.end(), [](const string& a, const string& b) {
    if (a.size() != b.size()) return a.size() < b.size();
    return a < b;
});

3. Closest to the origin. Given points, sort them by squared distance from (0, 0). Hint: squared distance is x * x + y * y, and it avoids a square root.

4. Predict the order. Without running it, predict the output of sorting (2, 9), (1, 7), (2, 3) as pairs, and print each pair. Hint: compare the first value, then the second.

5. Top three. Read n scores and print the top three in order, highest first. Hint: partial_sort with a third argument of begin() + 3.

6. Find the bug. The comparator below is meant to sort students by marks, highest first. It crashes on some inputs. Explain why, and fix it. Hint: look at the comparison operator.

sort(s.begin(), s.end(), [](const Student& a, const Student& b) {
    return a.marks >= b.marks;
});

7. Stable by hand. Given zoe 7, ann 3, bob 7, cam 3, write the output of stable_sort by score, lowest first. Hint: the 3s keep their order, and so do the 7s.

8. Positions, not values. Use argsort to print the 1-based position of the largest value in the array 4 9 2 9 1, choosing the first position for a tie. Hint: sort the positions by value descending with stable_sort, then read the first one.

9. Sort strings without case. Sort the words Banana apple Cherry alphabetically, ignoring case. Hint: compare the lower-case versions in the lambda.

10. Edge case. What does sort(v.begin(), v.begin(), cmp) do on an empty vector, and why is it safe? Hint: think about the range from start to end.

What you now know

• std::sort takes a range, from a start iterator up to one past the end, and sorts it in O(n log n) time.
• A comparator answers "should a come before b?" and must be a strict rule, using > or <, never >= or <=.
• Lambdas let you write comparators inline. Capture lists bring outside values into the rule.
• For a two-part rule, test the most important key first and the next key only when the first ties.
• std::stable_sort keeps the input order for ties. std::sort does not promise that.
• Argsort sorts positions instead of values, which is useful for ranks and for sorting one list while tracking another.
• Compiler messages name the file, line and reason. Read the first error line first.