Sorting and Ordering

Part I · Module 20 · Chapter 20.6 · Sorting and Ordering

1. sort, and the Comparator's Shape

std::vector<Txn> t{{0x3000,8,0},{0x1000,12,1},{0x4000,55,2},{0x2000,31,3}};
std::sort(t.begin(), t.end(), [](const Txn& a, const Txn& b){ return a.addr < b.addr; });

by addr  : 0x1000 0x2000 0x3000 0x4000
is_sorted by addr = 1

std::sort(b, e) orders a range using operator<; std::sort(b, e, comp) uses the comparator you supply. It requires random-access iterators — Chapter 20.2 §7 measured what happens on a std::list — and it is O(n log n) comparisons, guaranteed since C++11 rather than merely on average.

The comparator's contract is specific and worth stating exactly: comp(a, b) returns true if and only if a must come strictly before b. It is a less-than, not a "should these be swapped" and not a three-way comparison. Two consequences follow immediately:

• comp(a, a) must be false. An element is never strictly before itself.
• If comp(a, b) is true, then comp(b, a) must be false.

Both parameters should be const& — the comparator must not modify what it is ordering, and taking them by value copies every element on every comparison, which for a non-trivial type is real work multiplied by O(n log n).

2. Strict Weak Ordering

The full requirement has four parts, and the standard calls a relation satisfying them a strict weak ordering:

Irreflexive. comp(a, a) is false.

Asymmetric. comp(a, b) and comp(b, a) are never both true.

Transitive. If comp(a, b) and comp(b, c), then comp(a, c).

Transitive on equivalence. Define a and b as equivalent when neither comp(a, b) nor comp(b, a) holds. Then equivalence must itself be transitive: if a is equivalent to b and b to c, then a is equivalent to c.

The first three are what people expect. The fourth is the one that catches real comparators, and it is why "sort by whichever field is non-empty" and similar ad-hoc rules fail: they can make a equivalent to b and b equivalent to c while a and c compare.

Note the term weak: equivalent elements are permitted, and that is normal — sorting transactions by address makes two transactions at the same address equivalent. What is forbidden is equivalence that is not transitive.

Also note the comparator defines equivalence, not equality. operator== on your type is never called by sort. Chapter 19.5 §10 measured the same thing for std::map, where a case-insensitive comparator silently merges keys.

3. What a Violation Does

The natural mistake is <=:

auto bad = [](int a, int b){ return a <= b; };

good comparator: comp(5,5) = 0  (must be 0)
BAD  comparator: comp(5,5) = 1  (<= makes an element less than itself)

comp(5,5) returning true breaks irreflexivity, and that is not a technicality. std::sort's partitioning loops advance while the comparator says an element belongs on one side, and they rely on the comparator eventually saying "no" at the pivot. With <=, a run of equal elements never says no, and the loop runs off the end of the array.

Measured, on 2,000 identical elements — the worst case for <=:

plain -O2    : exit 138   (SIGBUS)
ASan         : ERROR: AddressSanitizer: heap-buffer-overflow
               READ of size 4 at ... 0 bytes after an 8000-byte region
               #0 in std::__introsort<...> sort.h:804
               exit 134
libc++ debug : sort.h:603: libc++ Hardening assertion __first != __end failed:
               Would read out of bounds, does your comparator satisfy the
               strict-weak ordering requirement?
               exit 134

Three different tools, three different reports, all pointing at the same thing — and the libc++ hardening assertion names the requirement in English, which is about as helpful as a diagnostic gets.

The contrast with the rest of this module is the point. Chapter 20.3's erase-in-a-loop bug was silent under -O0, -O2, ASan, UBSan and libc++ debug hardening. Chapter 20.5's unsorted binary_search was silent and is undetectable in principle. This one is caught by everything. The discriminator is not severity — it is whether the undefined behaviour crosses an allocation boundary, and a bad comparator drives the sort straight off the end of the buffer.

So: an invalid comparator is a bug you will find. That is good news, and it is also the reason this section can be short.

4. sort Is Not Stable, and a Small Test Will Not Tell You

std::sort makes no promise about the relative order of equivalent elements. std::stable_sort promises to preserve their original order.

The obvious way to check is to sort a few records with equal keys and look. That does not work, and finding out why is more useful than the rule:

sort        equal-latency order: 4 0 1 2 3 5 6 7 8 9 ...
stable_sort equal-latency order: 4 0 1 2 3 5 6 7 8 9 ...
did plain sort preserve the original order of equals? yes -- AT THIS SIZE

At twenty elements, plain sort was stable. Sweeping the size finds where that stops:

n=8,16       sort stable
n=32,64,128  sort REORDERS equals (2 distinct keys)
n>=1000      sort REORDERS equals always
stable_sort  stable at EVERY size tested

Stable at 16, unstable at 32. The reason is implementation strategy: libc++ switches to insertion sort below a threshold, and insertion sort happens to be stable. Above it, the introsort machinery partitions and the order of equivalents is lost.

This is the worst possible behaviour for a guarantee you do not have: it holds on small inputs, which is exactly what a unit test uses, and fails on production-sized data. If equal-element order matters, std::stable_sort is not an optimisation question — it is the only correct call.

stable_sort costs something for the promise: it is O(n log n) if it can allocate a temporary buffer and O(n log² n) if it cannot, where sort is O(n log n) with no allocation. In practice the difference is small and the correctness is not negotiable.

5. Doing Less Work for Less Information

Three algorithms sort partially, and the savings are large enough to matter.

sort (all 200000)                     12.82 ms
partial_sort (top 10)                  0.11 ms
nth_element (median)                   1.91 ms
partial_sort is 119.0x faster, nth_element 6.7x

partial_sort(b, mid, e) fully sorts [b, mid) and leaves [mid, e) unspecified. For the top ten of two hundred thousand it was 119× faster than sorting everything, because it is O(n log k) in the number of elements you actually asked for.

nth_element(b, nth, e) puts the element that would be at nth in a fully sorted range into that position, and partitions everything else around it. O(n) on average. Measured 6.7× faster than a full sort, and the guarantee is exactly:

element 100000 is in its final place (499638); left all <= : 1, right all >= : 1
but neither side is SORTED -- that is the work it skipped
left side sorted? 0

So after nth_element at the midpoint you have the median, and you know everything to its left is no greater and everything to its right is no smaller — and neither side is in order. That is the right tool for a percentile and the wrong tool if you then want to print the sorted lower half. Chapter 20.10 §4 uses it three times to get median, p90 and p99.

partition(b, e, p) splits a range into the elements satisfying a predicate and those not, returning the boundary, in one pass with no allocation. stable_partition additionally keeps each group in its original order. When you want both halves, this beats two copy_if passes — Chapter 20.10 §7 measures it splitting 20,000 transactions in one pass.

partition_point(b, e, p) is the binary search over an already-partitioned range, with the same precondition logic as Chapter 20.5 §6.

6. Sorting by Several Keys

The pattern is a sequence of comparisons, falling through to the next key when the current one ties:

std::sort(t.begin(), t.end(), [](const Txn& a, const Txn& b){
    if (a.addr != b.addr) return a.addr < b.addr;      // primary
    return a.latency < b.latency;                      // tie-break
});

by (addr, latency): (0x1000,5) (0x1000,10) (0x2000,5) (0x2000,10)

That is correct and it is easy to get wrong — the classic error is writing return a.addr < b.addr || a.latency < b.latency;, which is not transitive and so not a valid ordering at all.

std::tie removes the opportunity:

std::sort(u.begin(), u.end(), [](const Txn& a, const Txn& b){
    return std::tie(a.addr, a.latency) < std::tie(b.addr, b.latency);
});

by std::tie       : (0x1000,5) (0x1000,10) (0x2000,5) (0x2000,10)

Identical result. std::tie builds a tuple of references, and operator< on a tuple is lexicographic — compare the first elements, and only on a tie move to the second. It is guaranteed to be a valid strict weak ordering if each member's < is, it extends to any number of keys by adding them to both lists, and it cannot be written in the wrong order without the mistake being visible.

For descending on one key inside a multi-key sort, negate that one comparison rather than reversing the whole tuple:

return std::tie(a.addr, b.latency) < std::tie(b.addr, a.latency);   // latency DESCENDING

— note the swapped a/b on the second element only. This works and is clever enough to deserve a comment.

In C++20, a defaulted operator<=> on the struct generates lexicographic member-wise comparison for you, which is better than all of the above when the member order is the sort order.

7. Descending, and Other Orders

std::greater<int>{} : 5 4 3 1 1
sort(rbegin,rend)   : 5 4 3 1 1

Both work. std::greater<T>{} passed as the comparator is the clearer of the two; sorting the reverse iterators achieves the same thing and reads as a trick. Note std::greater is a valid strict weak ordering — it is a strict >, not >=.

Related orderings worth knowing: std::sort with a projection is not available until C++20's ranges (std::ranges::sort(v, {}, &Txn::addr) is the modern form and is considerably nicer); std::shuffle(b, e, gen) randomises, taking a random engine rather than the removed random_shuffle's global state; and std::reverse is not a sort at all but is often what someone reaching for a descending sort actually wants on already-sorted data.

8. Which Sort to Call

9. Sorting Expensive Elements

When the element is large, sorting moves it repeatedly. Two standard responses.

Sort indices or pointers instead, and leave the data where it is:

std::vector<std::size_t> idx(data.size());
std::iota(idx.begin(), idx.end(), 0);
std::sort(idx.begin(), idx.end(),
          [&](std::size_t a, std::size_t b){ return data[a].addr < data[b].addr; });

Now the sort moves eight-byte indices rather than whole records, and data is untouched — which is useful when you want several orderings of the same data, or when the data must keep its addresses stable.

The caution is Chapter 19.8 §4's: accessing data[idx[i]] afterwards is a scattered access pattern, and that was measured at roughly sixty times the cost of a sequential one. So this wins when the element is large and the subsequent access is light, and loses when the element is small and you then traverse the whole thing.

Make the element cheap to move. Chapter 13.8 §7's noexcept move is the mechanism: sort moves elements, and a type whose move is a pointer swap is cheap to sort regardless of how much it owns. This is usually the better answer.

10. What to Actually Do

• Write <, never <=. Measured: <= is a SIGBUS at 2,000 equal elements.
• Take comparator parameters by const&. No copy per comparison, and no accidental modification.
• Use std::stable_sort whenever equal-element order is part of the answer. Measured: sort is stable at 16 and not at 32, so testing cannot tell you.
• Use std::tie for multi-key comparators, so the non-transitive || form cannot be written.
• Use partial_sort for the top k — 119× measured — and nth_element for a percentile.
• Remember nth_element leaves both sides unsorted. Measured.
• Use partition / stable_partition when you want both halves, not two copy_if passes.
• Use std::greater<T>{} for descending, not reversed iterators.
• Sort indices when the element is large — but check Chapter 19.8 §4's scatter cost before assuming it wins.
• Mark your type's move noexcept, which is usually a better answer than sorting indices.
• Guard with is_sorted in debug builds wherever a later binary search depends on the order.

11. Mistakes Worth Making Once

a <= b as a comparator. SIGBUS, caught by everything, and the libc++ message names the cause. The best kind of bug.

a.x < b.x || a.y < b.y for two keys. Not transitive, so not a valid ordering; use std::tie.

Relying on sort being stable because a small test showed it was. Measured stable at 16 and unstable at 32.

max_element with std::greater — or sort with >=. The second is the comparator bug again.

Calling nth_element and then printing one side as if sorted. Measured: left side sorted? 0.

Taking comparator parameters by value for a type with a heap buffer. One copy per comparison, O(n log n) times.

std::sort on a std::list. Four errors, 138 lines — Chapter 20.2 §7.

Sorting indices and then traversing the whole dataset through them. Chapter 19.8 §4's scattered access, measured at around 60×.

12. Interview Relevance

The frozen curriculum marks this chapter High, and the comparator requirement is the discriminating question.

"What must a comparator satisfy?" A strict weak ordering: irreflexive, asymmetric, transitive, and with transitive equivalence. The fourth part is the one that distinguishes a read answer from a remembered one.

"What happens if it does not?" Undefined behaviour — and specifically, std::sort reads past the end of the range. Quoting SIGBUS, the ASan heap-buffer-overflow and the libc++ assertion makes the answer concrete.

"Why is a <= b wrong?" It makes an element compare less than itself, breaking irreflexivity, and the partition loop never terminates inside a run of equal elements.

"Is std::sort stable?" No, and the strong answer continues: a small test may suggest otherwise because implementations insertion-sort short ranges, measured stable at 16 and unstable at 32.

"When would you use nth_element?" A percentile or a median, where O(n) beats O(n log n) — measured 6.7× — and where you do not need either side ordered.

"How do you sort by two keys?" std::tie on both sides, which is lexicographic and guaranteed valid. Mentioning that the || form is non-transitive is the detail.

"How do you sort a large struct cheaply?" Make its move noexcept, or sort indices — and know that indices trade move cost for a scattered access pattern afterwards.

13. What You Should Be Able to Say Now

• That a comparator is a strict <, takes const&, and must be a strict weak ordering — all four conditions.
• That the comparator defines equivalence and operator== is never consulted.
• That <= is a SIGBUS at scale, caught by -O2, ASan, UBSan and libc++ hardening — and why this module's other two bugs are not caught at all.
• That std::sort is unstable, measured stable at n=16 and unstable at n=32, so a small test cannot establish it.
• That stable_sort is the only correct call when equal-element order matters.
• That partial_sort was 119× faster for the top 10 of 200,000 and nth_element 6.7× for the median.
• That nth_element leaves both sides unsorted — measured.
• That std::tie is the safe multi-key comparator and the || form is non-transitive.

14. Exercises

Exercise 1 — the bad comparator. Reproduce §3 at 2,000 equal elements under all four configurations and record each diagnostic. Then find the smallest element count at which it still crashes.

Exercise 2 — the stability threshold. Reproduce §4's sweep on your implementation and report the n at which sort stops being stable. Explain the number in terms of the insertion-sort cutoff.

Exercise 3 — non-transitive. Write the a.x < b.x || a.y < b.y comparator, find three elements that demonstrate the failure of transitivity, and then sort 10,000 records with it under ASan.

Exercise 4 — tie. Rewrite three multi-key comparators from your own code using std::tie and verify the orders are unchanged. Then make one key descending.

Exercise 5 — partial. Measure sort, partial_sort and nth_element across k = 1, 10, 100, 1000, 10000 for a fixed n. Plot the three and find where partial_sort stops winning.

Exercise 6 — what nth_element promises. After nth_element at the midpoint, verify by assertion that the three guarantees hold and that neither side is sorted.

Exercise 7 — indices versus elements. Sort a vector of 256-byte structs directly and via an index vector. Measure the sort and then measure a full traversal in sorted order through each.

Exercise 8 — noexcept. Give a type with a heap buffer a noexcept move, sort a million of them, remove the noexcept, and compare.

15. Summary

• std::sort is O(n log n) guaranteed, requires random access, and takes a comparator that must be a <.
• A comparator must be a strict weak ordering — irreflexive, asymmetric, transitive, and transitive on equivalence — and it defines equivalence, not equality.
• Measured: a <= b on 2,000 equal elements gives SIGBUS (exit 138), an ASan heap-buffer-overflow 0 bytes past an 8000-byte region inside sort.h:804, and a libc++ assertion naming strict weak ordering outright. All four tools catch it — unlike Chapter 20.3's erase bug, which all four miss.
• std::sort is NOT stable. Measured stable at n=8 and 16, reordering equals from n=32, always from n=1000 — because libc++ insertion-sorts short ranges. A small test cannot establish stability.
• std::stable_sort was stable at every size tested and is the only correct call when equal order matters.
• Measured: partial_sort for the top 10 of 200,000 was 119× faster than a full sort; nth_element for the median 6.7×.
• Measured: nth_element puts one element in its final place and partitions around it — and leaves both sides unsorted.
• Use std::tie for multi-key comparators; the a.x < b.x || a.y < b.y form is not transitive.
• For large elements, prefer a noexcept move to sorting indices, because indices buy cheap moves and pay Chapter 19.8 §4's scattered access afterwards.

Searching asked where an element is and sorting decided what order means. Chapter 20.7 covers the two remaining shapes of operation over a range: producing a new range from an existing one, and reducing a range to a single value. The second of those contains the module's quietest defect — an accumulation whose answer is decided not by the data or the operation but by the type of the initial value, where writing 0 instead of 0.0 turned a sum of 8.00 into 6, with no warning from -Wall, -Wextra, -Wconversion or even -Weverything.