1. Sorting as an operation
When we say "to sort", in everyday terms it sounds simple: "make it ascending". But for a programmer it's useful to be more precise: sorting is an algorithm that rearranges elements in a given range [first, last) so that they follow the required order. In the C++ standard, sorting algorithms are grouped into a dedicated topic area, and that's not accidental: sorting is one of the main tools for working with data.
Almost all STL sorts follow the same mental model:
- there is a sequence of elements (for example, std::vector<Task>);
- there is a rule "who should come earlier" (by default — via operator<);
- the algorithm rearranges elements so that the rule holds everywhere.
Mini thinking diagram
flowchart LR
A["vector<Task> (as is)"] --> B["ordering rule (operator< or comp)"]
B --> C["sort/stable_sort"]
C --> D["vector<Task> (ordered)"]
2. std::sort: fast, but no promises for "equal" elements
std::sort is the STL "workhorse". It is usually the first choice: fast, familiar, and almost always "good enough". It is important to remember right away: std::sort does not guarantee that elements with equal keys will preserve their original relative order. That is, if you have several "equal in meaning" elements — they may swap places.
From a beginner's point of view that sounds like "so what?". But from the perspective of someone who debugged "why the list suddenly jumps" — it sounds like "ah, here it is".
Minimal example: sorting numbers
After this subsection you should feel that sorting in the STL is literally "one line". We'll start with the simplest: sorting int. No comparator is needed here: numbers already compare via <.
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v{5, 1, 4, 1, 3};
std::sort(v.begin(), v.end());
for (int x : v) std::cout << x << ' ';
std::cout << '\n'; // 1 1 3 4 5
}
The syntax is always the same: include <algorithm>, pass the beginning and the end of the range.
std::sort with a comparator: sorting in descending order
Now we complicate the task a bit: we want the opposite order. For that std::sort accepts a third parameter — a comparator. A comparator is a function of the form bool comp(a, b) that answers the question "should a come before b?".
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v{5, 1, 4, 1, 3};
std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; });
for (int x : v) std::cout << x << ' ';
std::cout << '\n'; // 5 4 3 1 1
}
We will discuss what a comparator must be (and why a "slightly wrong" comparator can break the algorithm) in the next lecture. For now it's important only that: the comparator defines the order.
3. Sorting stability and std::stable_sort
Here begins the main idea of the lecture. Sorting stability is not about "faster/slower" but about the meaning of the result.
Imagine you have a task list and each task has a priority. If two tasks have the same priority, usually we want them to remain in the same order as they were added (or loaded). This original order often carries meaning: "show as they arrived".
Stable sorting guarantees: if elements are considered "equal by the sorting key", then their relative order is preserved.
If a sort is unstable, equal elements may be shuffled arbitrarily. This is not a bug — it's the absence of a guarantee.
std::stable_sort differs from std::sort by exactly one key guarantee: stability. Otherwise the interface is the same: [begin, end) and an optional comparator.
A practical point: stability usually "costs something". Most often it's either a bit more time, or extra memory, or both (details depend on the implementation). So enable stability when you really need it, not "just in case".
Data model for examples: Task
From this subsection we'll start building a small application: a mini task manager in the console. It has already appeared in various forms in previous topics (containers, structs, output), and today we'll add sorting "like in real apps", not "like in a 7th-grade test".
#include <iostream>
#include <string>
#include <vector>
struct Task {
int id{};
int priority{}; // the smaller the more important (0 — urgent)
std::string title;
};
int main() {
std::vector<Task> tasks{
{1, 2, "Buy milk"},
{2, 1, "Send report"},
{3, 2, "Call mom"},
{4, 1, "Fix bug #42"}
};
std::cout << "Tasks loaded: " << tasks.size() << "\n";
}
So far this is just data. Now we will add printing and sorting.
Function to print tasks
If you don't print the result — sorting becomes philosophy. So let's make a small printTasks function. It will be needed today and in following lectures.
#include <iostream>
#include <string>
#include <vector>
struct Task {
int id{};
int priority{};
std::string title;
};
void printTasks(const std::vector<Task>& tasks) {
for (const auto& t : tasks) {
std::cout << "#" << t.id << " p=" << t.priority
<< " " << t.title << '\n';
}
}
Note the parameter const std::vector<Task>&. We do not copy the whole task list just to print it.
Sorting tasks by priority using std::sort
Now the most straightforward step: "sort by priority". We write a comparator and call std::sort.
#include <algorithm>
#include <vector>
void sortByPriority(std::vector<Task>& tasks) {
std::sort(tasks.begin(), tasks.end(),
[](const Task& a, const Task& b) {
return a.priority < b.priority;
});
}
This works. But there is a nuance: we have two tasks with priority 1 and two with priority 2. The order inside these groups std::sort is not required to be preserved.
If you are lucky — "on your machine" it will look stable. If not — tasks inside a priority may swap places, and the user will think the app is "unstable".
4. Stability in practice: "jumping" elements and the solution
Stability is most often needed not "for beauty" but to avoid strange UX. Let's assume the rule: within the same priority tasks should be shown in insertion order (that is, by id, because we added them sequentially).
If we use std::sort only by priority, two tasks with the same priority may swap places. And formally the algorithm is correct.
To make it easier to see, we'll print tasks before and after.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Task {
int id{};
int priority{};
std::string title;
};
void printTasks(const std::vector<Task>& tasks) {
for (const auto& t : tasks) {
std::cout << "#" << t.id << " p=" << t.priority
<< " " << t.title << '\n';
}
}
int main() {
std::vector<Task> tasks{
{1, 2, "Buy milk"},
{2, 1, "Send report"},
{3, 2, "Call mom"},
{4, 1, "Fix bug #42"}
};
std::cout << "Before:\n";
printTasks(tasks);
std::sort(tasks.begin(), tasks.end(),
[](const Task& a, const Task& b) {
return a.priority < b.priority;
});
std::cout << "\nAfter sort by priority:\n";
printTasks(tasks);
}
The "after" result only guarantees that priorities appear as 1, 1, 2, 2. Which of the two tasks with priority == 1 appears first is not promised.
Now the same sorting, but stable. We just change sort to stable_sort. The interface is the same, the guarantee is different.
#include <algorithm>
#include <vector>
void stableSortByPriority(std::vector<Task>& tasks) {
std::stable_sort(tasks.begin(), tasks.end(),
[](const Task& a, const Task& b) {
return a.priority < b.priority;
});
}
Now the rule "inside the same priority the order is as before" is satisfied automatically.
This is usually what applications want: the user didn't ask you to "randomize tasks with the same priority". They asked to "sort". Stability makes sorting more predictable.
5. When stability really matters
It's easy to fall into the extreme: "stable_sort is better because it's safer". But in programming "better" almost always means "better for specific requirements". Otherwise it may mean "slower and more memory-hungry without benefit".
Scenario: the original order carries meaning
A very common case: you have data in some order, and that order already means something. For example, "as it came from the server", "as the user added it", "as it lies in the file". You want to sort by one key but keep the original order within equals. This is a direct case for std::stable_sort.
Our Task is exactly such an example: if priority is equal, we want to keep insertion order.
Scenario: multi-step sorting
This scenario is especially nice because it shows why stability is useful even for those "not about UX but about algorithms".
Suppose we want the order: first by priority, and inside a priority — by title. You could write a single comparator "if priorities are equal, compare title" — and that will be the topic of the next lecture (on comparators and correct ordering).
But there is another approach: perform sorting in two passes, and then stability becomes the tool. First sort by the secondary key (title), then stably sort by the primary key (priority). Stability guarantees that within equal priority the established order by title is preserved.
#include <algorithm>
#include <string>
#include <vector>
void sortByPriorityThenTitle(std::vector<Task>& tasks) {
std::sort(tasks.begin(), tasks.end(),
[](const Task& a, const Task& b) {
return a.title < b.title; // secondary key
});
std::stable_sort(tasks.begin(), tasks.end(),
[](const Task& a, const Task& b) {
return a.priority < b.priority; // primary key
});
}
This technique is often used when there are many keys and you don't want to write a huge comparator. Yes, in performance terms this is two O(N log N) passes, so use it wisely. But as a concept — it's very useful.
6. sort vs stable_sort: a "by-hand" comparison
Now it's useful to fix the differences in one table. It's not about "internal implementation" but about what promises you get as a user of the algorithm.
| Criterion | |
|
|---|---|---|
| Stability guarantee | No (equal elements may change order) | Yes (preserves order of elements equal by key) |
| Typical default choice | Yes | Only if stability is needed |
| Memory/cost | Usually more economical | Usually more expensive (often requires extra memory) |
| Where more useful | "Just sort" | UX lists, reports, multi-step sorts |
The phrase sorted with respect to comp is an important standard idea: after sorting the range must be "sorted according to the comparator", not "just roughly ordered".
7. Integration into an application: sort mode
To make this concrete, let's add a switch in main: sort with regular or stable sorting. This looks more like a real program: the user chooses a mode and you show the result.
After this subsection you should pick up a useful habit: hide sorting in small functions (sortBy...), and keep main as the scenario orchestrator.
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Task {
int id{};
int priority{};
std::string title;
};
void printTasks(const std::vector<Task>& tasks) {
for (const auto& t : tasks) {
std::cout << "#" << t.id << " p=" << t.priority
<< " " << t.title << '\n';
}
}
void sortByPriority(std::vector<Task>& tasks, bool stable) {
auto comp = [](const Task& a, const Task& b) {
return a.priority < b.priority;
};
if (stable) {
std::stable_sort(tasks.begin(), tasks.end(), comp);
} else {
std::sort(tasks.begin(), tasks.end(), comp);
}
}
int main() {
std::vector<Task> tasks{
{1, 2, "Buy milk"},
{2, 1, "Send report"},
{3, 2, "Call mom"},
{4, 1, "Fix bug #42"}
};
std::cout << "Before:\n";
printTasks(tasks);
sortByPriority(tasks, true);
std::cout << "\nAfter stable sort by priority:\n";
printTasks(tasks);
}
Here we did an important thing: the same comparator (comp) is used for both algorithms, and the selection logic is hidden in one place.
8. Typical mistakes when working with sort and stable_sort
Mistake #1: expecting stability from std::sort.
A very common trap: you sort by one field and "seem" to see equal elements in the original order. Then the compiler changes, the dataset changes, optimization changes — and the order inside equal keys starts to "jump". If the order of equals matters (UI, report, task list) — use std::stable_sort, don't rely on luck.
Mistake #2: thinking stability is "always better".
Stability is an extra guarantee, and guarantees usually cost something. If the order of equal elements doesn't matter, std::sort will be simpler and often cheaper. A good engineering habit: pay only for guarantees you really need.
Mistake #3: confusing the meaning of the comparator.
Beginners sometimes write a comparator as if it answers "should a be greater than b?" or even "are elements equal?". In sorting the comparator is read as "a should go before b". The correctness rules for a comparator (including nasty cases when the algorithm may behave oddly) will be covered in the next lecture — and that's one area where improvisation is risky.
Mistake #4: doing a two-step sort but forgetting stability in the second step.
A classic slip: first you sort by the secondary key, then do a second pass with regular std::sort by the primary key and wonder why the secondary order is gone. In a two-step scheme the second step must be stable, otherwise it will destroy the result of the first step.
Mistake #5: sorting "inside print" or in random places in the code.
Sometimes sorting is inserted right before output, inside the printing function, or in multiple places at once. Then "ghosts" appear: the data seems the same, but the order is different. Keep sorting in one place, in a separate function, and call it explicitly — that way you control the moment when the data is "rearranged".
GO TO FULL VERSION