skip to content

A C++ std::sort call using the comparator [](int a, int b) { return a <= b; } hangs or crashes on many equal scores; why?

level: seniorimportance: should knowfreq 50%

answer

  1. irreflexive: comp(x, x) is false
  2. transitivity of equivalence too
  3. sentinel-free inner loops
  4. NaN breaks it as well
  5. libc++ debug hardening catches it

basics

~20 s

std::sort requires the comparator to be a strict weak ordering. a <= b returns true for equal values, so it is not irreflexive, and the program has undefined behaviour: optimised partition loops that trust the comparator can run past the range or never terminate.

solid answer

~40 s

The standard requires every comparator passed to `std::sort` to induce a **strict weak ordering**: `comp(x, x)` is false, `comp` is transitive, and equivalence (`!comp(a, b) && !comp(b, a)`) is transitive too. `a <= b` is true for equal elements, so it is not irreflexive, and because the comparator does not meet its requirements the behaviour is undefined - not merely a wrong order. Implementations rely on the property: introsort's partition and unguarded insertion-sort loops stop only when the comparator returns false against a pivot or a known smaller element, so `<=` lets them walk past the range. Other common violations are floating-point keys containing NaN and "approximately equal" comparisons with a tolerance. libc++'s `debug` hardening mode reports the bug; libstdc++'s `_GLIBCXX_DEBUG` checks only that the first element is not less than itself.

code

cpp · 11 lines
cpp
#include <algorithm>
#include <cstdio>
#include <vector>

int main() {
    std::vector<int> scores(64, 500);   // many equal scores
    // BUG: <= is not irreflexive, so it is not a strict weak ordering
    std::sort(scores.begin(), scores.end(),
              [](int a, int b) { return a <= b; });
    std::printf("sorted %zu scores\n", scores.size());
}

go deeper

for a junior

Remember the rule of thumb: a sort comparator uses < or >, never <= or >=.

for a middle

Name the three properties of a strict weak ordering and show why <= fails irreflexivity and a NaN key fails transitivity of equivalence.

for a senior

Diagnose a crash or hang inside std::sort as undefined behaviour from the comparator, explain the unguarded loops, and reach for libc++ debug hardening or _GLIBCXX_DEBUG to confirm.

for a principal

Make debug-hardened standard library builds and duplicate-heavy sort tests part of continuous integration so comparator bugs never reach release builds.

## The requirement For every sorting-related algorithm except the binary searches, the standard says `comp` **shall induce a strict weak ordering**. Spelled out: 1. **Irreflexive:** `comp(x, x)` is `false` for every `x`. 2. **Transitive:** `comp(a, b) && comp(b, c)` implies `comp(a, c)`. 3. **Transitive equivalence:** with `equiv(a, b)` defined as `!comp(a, b) && !comp(b, a)`, `equiv(a, b) && equiv(b, c)` implies `equiv(a, c)`. Under these rules equivalence is a real equivalence relation and `comp` totally orders its classes, which is what every partition step assumes. A comparator that violates them is a user-supplied component that does not meet its requirements, and the library-wide rule for that case is that the standard places no requirements on the implementation: **undefined behaviour**. For `std::ranges::sort` the same requirement is the semantic part of the `std::strict_weak_order` concept behind `std::sortable`; it compiles because the syntax is satisfied, and the behaviour is still undefined. ## Why <= breaks the machinery Quicksort-style partitioning and insertion sort are fastest when the inner loop has no bounds check. A typical inner loop moves an index while `comp(*i, pivot)` is true and relies on the guarantee that some element - the pivot itself, or a median-of-three element placed at the end - stops it, because `comp(pivot, pivot)` is false. Insertion sort similarly runs "unguarded" once the smallest element is known to be at the front. With `a <= b`, `comp(pivot, pivot)` is **true**. On a range full of equal scores every comparison returns true, so the loop does not stop at the sentinel and keeps reading past the end of the range. Depending on what lies beyond, you get a segmentation fault, corrupted neighbouring memory, a sort that never finishes, or a range containing duplicated and lost elements. On Apple clang 21 with libc++, a plain build of the example below did not return within five seconds. ## Other ways to break the ordering | Comparator | Broken property | |---|---| | `a <= b`, `a >= b` | irreflexivity | | `a < b` on doubles containing NaN | equivalence transitivity: NaN is equivalent to both 1.0 and 2.0 | | `a < b - eps` ("roughly less") | equivalence transitivity: 1.0 ~ 1.4 ~ 1.8 but 1.0 < 1.8 | | comparing `score` in one branch and `name` in another inconsistently | transitivity | | a comparator that reads mutable or random state | every property, unpredictably | NaN is the one that ships to production: a single NaN key from a division by zero is enough. Filter NaNs out first, or compare with `std::strong_order(a, b) < 0` (C++20), which for floating-point values gives a total order that includes NaN and, on IEEE 754 platforms, follows its `totalOrder` operation. ## Detecting it - **libc++ hardening.** With `-D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_DEBUG`, libc++ checks the "would read out of bounds" guards and, after sorting, that the range is sorted and that the first 100 elements are consistently ordered. The `fast` and `extensive` modes keep the out-of-bounds guard (its valid-element-access category) but not the semantic-requirement checks; in `fast` mode on Apple clang 21 the example stopped with a trap instead of a message. - **libstdc++ debug mode.** `-D_GLIBCXX_DEBUG` adds an irreflexivity check, `!comp(*first, *first)`, which catches `<=` but not NaN or tolerance bugs. - **Sanitizers.** AddressSanitizer reports the out-of-bounds read when the loop leaves the allocation, but only if it does. - **Unit tests** that sort ranges full of duplicates and assert `std::is_sorted` catch most of these before production. ## What an interviewer listens for The strongest answers name three things in order. First, the rule: the comparator must be a strict weak ordering, and `<=` fails irreflexivity. Second, the consequence: this is undefined behaviour, not a wrong but valid order, because the standard library is allowed to assume the rule and does. Third, the mechanism: sentinel-based inner loops trust `comp(pivot, pivot)` to be false, so equal elements let them run past the range. A candidate who adds how to catch it - a debug-hardened standard library build in continuous integration, plus tests that sort ranges with many duplicates - shows they have met the bug outside a whiteboard. ## Fixing it - Use a strict comparison: `<` for ascending, `>` or `std::greater<>{}` for descending. - For several keys, compare `std::tie(...)` tuples rather than hand-writing branches. - Keep keys well-defined: no NaN, no tolerances, no state that changes during the sort. - If "close enough" grouping is the goal, quantise the key first (round to a bucket) and sort by the bucket.

  • Why can a vector of doubles containing a NaN break std::sort with the default operator<?
    Every comparison with NaN is false, so NaN is equivalent to every number. Then NaN ~ 1.0 and NaN ~ 2.0, yet 1.0 < 2.0, so equivalence is not transitive and `operator<` is not a strict weak ordering on that data. The behaviour is undefined. Remove NaNs first, or sort with `std::strong_order` (C++20), which totally orders floating-point values including NaN.
  • Which build switches make libc++ and libstdc++ report a bad comparator?
    libc++: `-D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_DEBUG` turns on the semantic-requirement checks that verify the sorted result and the ordering of the first 100 elements; the `fast` mode only keeps the out-of-bounds guard. libstdc++: `-D_GLIBCXX_DEBUG` enables a check that `comp(*first, *first)` is false, which catches `<=` but not NaN or tolerance comparators.

  • Saying a bad comparator just produces a slightly wrong order
  • Believing <= is fine because the output looked sorted in a test
  • Calling operator< on doubles always a valid ordering
  • Comparing with a tolerance to make sorting robust
  • Assuming std::ranges::sort rejects a bad comparator at compile time

Assumes C++23; the strict weak ordering requirement is the same in every standard, while std::ranges::sort and std::strong_order are C++20 additions.