My earlier discussion of sorting introduced an idea that is worth stating more explicitly: Sorting a sequence stably preserves earlier orderings where they don't conflict. In other words, if you sort a sequence, and then sort it again under different criteria, the original ordering is preserved as much as possible. Moreover, there is no need to use the values of the sequence's elements directly. It can be useful to sort those elements based on indirect criteria.

Here's a simple example that shows where these properties might be useful. Suppose you have a sequence of student grade records, which you have sorted into alphabetical order by student name. Suppose that you now sort these records by grade. Each group of students with exactly the same grade will still appear in alphabetical order within that group.

This claim may seem obvious. What may be less obvious is that the claim remains true even if there are only two possible grades: pass and fail. We can exploit this property by writing a "comparison" function along these lines:

bool check_passfail(const Student& s1, const Student& s2)
 {
       return !s1.pass() && s2.pass();
 }

Here, by way of an unrealistically simple example, I am imagining a class Student with a member function named pass that returns true if the student is passing and false if the student is failing. I've written a function named check_passfail that, given two Students, returns true if and only if the first Student is failing and the second one is passing.

What happens if we use this function as a comparison function in a stable sort?

stable_sort(students.begin(), students.end(), check_passfail);

Because of how stable sorting works, students will be rearranged so that the "smallest" students — that is, the ones that are failing — will be at the beginning of the sequence, and the others will be at the end. In other words, the sequence will be divided into two subsequences. The first subsequence will contain all the failing student records; the second will contain all the passing students. Moreover, because the sort is stable, within each group, any previous order will be retained.

Therefore, if we first sort our sequence of students by name, and then use stable_sort to group them into passing and failing, each group will remain sorted by name.

This example shows that the idea of sorting includes, as a special case, what we often think of as partitioning. We have a collection of values that we want to collect into categories. The number of categories might be as small as two, as we have illustrated here, or might be larger.

Whatever the number, as long as it is possible for us to look at two elements of the sequence and determine whether the first element should go into a category that (strictly) precedes the second element's category, we can write a "comparison" function that stable_sort can use to rearrange the sequence's elements appropriately. Moreover, if the sort is stable, it will preserve any previously existing order within each individual category.