The Sort That Crashes at 40 Jobs: Strict Weak Ordering
A scheduling service keeps a std::vector<Job> where:
struct Job { int priority; int id; std::string name; };
Jobs are sorted with:
std::sort(jobs.begin(), jobs.end(),
[](const Job& a, const Job& b) { return a.priority <= b.priority; });
Unit tests with 12 jobs and distinct priorities pass on every platform. In staging, 40 jobs are loaded, six pairs share a priority, and the service segfaults inside std::sort; the backtrace lands in std::__insertion_sort on libstdc++ and in std::__sort5 on libc++. The crash is reproducible with 40 jobs, disappears with 10, and also disappears when all priorities are unique. A junior developer proposes replacing <= with <, and a senior developer says that alone is still not enough because jobs with equal priority must keep insertion order. The service must preserve input order for equal priorities and must run on both libstdc++ and libc++ in release builds with -O2.
1. Explain why `<=` violates the comparator requirements and how that leads to out-of-bounds access. Then explain why 10 jobs pass but 40 jobs crash, and why unique priorities hide the problem.
Read the worked answer
std::sort requires a strict weak ordering. <= fails irreflexivity: comp(x, x) is true because x.priority <= x.priority. Introsort's insertion-sort phase and its partition loops rely on comp(x, x) == false; when it is true, the algorithm can move the cursor past the beginning or end of the range and read out of bounds. The result is undefined behavior, so a crash, silent corruption, or apparently correct output are all possible. The 12-job tests do not crash because the implementation uses insertion sort for small ranges and the invalid comparison happens not to drive the cursor out of bounds; with 40 jobs, quicksort partitions first and the insertion-sort chunks are larger, so the bad branch is reached. Unique priorities hide the bug because the comparator only differs from < when two priorities are equal; with six tied pairs, the <= path is exercised. The std::__insertion_sort frame is the tell-tale sign; the exact function name varies by standard library.
2. Evaluate the junior developer's fix. Is `<` sufficient? Explain the senior developer's objection and give two correct alternatives, including their trade-offs.
Read the worked answer
Changing <= to < restores a strict weak ordering: < is irreflexive, asymmetric, and transitive, and jobs with equal priority become equivalent. That eliminates the undefined behavior, but std::sort is not stable, so the six tied groups may be reordered. The senior developer is right: if input order must be preserved for equal priorities, use either a tie-breaker that encodes insertion order, return a.priority != b.priority ? a.priority < b.priority : a.id < b.id;, provided id is unique and increases with arrival, or use std::stable_sort with <. The tie-breaker is usually faster and gives deterministic output, but it changes the meaning of the key; document it. A monotonically increasing sequence number assigned at enqueue time is safer than a database id that may not reflect arrival order. Either way, test with at least 40 jobs and six tied priorities, and compare the full output order, not just the first element.
3. The team asks whether `std::stable_sort` with the original `<=` comparator would be safe, since stable sort never uses the crashing quicksort partition. Answer that question and justify the correct sequence of changes.
Read the worked answer
No. std::stable_sort also requires a strict weak ordering; the standard places the same comparator requirements on it. Merge sort compares elements and, with a comparator that says an element is less than itself, can consume elements past the end of a run or produce an inconsistent merge. It may crash less often than introsort in a given implementation because its access pattern is different, but that is not safety; it is undefined behavior with a different symptom, and it can change with optimization level, standard library, or input size. The only correct sequence is to repair the comparator first, then decide between sort and stable_sort based on whether stability is required. If stability is required, stable_sort with the fixed < comparator is correct and does not need an id tie-breaker; if a total order on (priority, id) is acceptable, plain sort with the tie-breaker is simpler and avoids the extra memory of stable_sort.