Comparator Contracts and Why a Bad One Crashes the Sort

A library sort is a function of two arguments: the data, and a comparison predicate. The predicate is not a hint about preference; it is a total specification of order, and the sort’s correctness proof assumes it behaves in a particular way. When the predicate breaks that assumption, the sort does not return a slightly wrong answer. It reads past the end of the array, recurses without terminating, or throws an exception from deep inside a library routine that has no idea what went wrong.

The four requirements

Every general-purpose sort in a standard library documents the same precondition, under slightly different names. In C++ it is strict weak ordering; in Java it is a comparator consistent with equals; in both cases the requirements on the relation $\prec$ (“compares less than”) are:

1. Irreflexivity. $x \prec x$ is false for every $x$.
2. Asymmetry. If $x \prec y$ then $y \prec x$ is false.
3. Transitivity. If $x \prec y$ and $y \prec z$ then $x \prec z$.
4. Transitivity of incomparability. If $x$ and $y$ are incomparable (neither $x \prec y$ nor $y \prec x$) and $y$ and $z$ are incomparable, then $x$ and $z$ are incomparable.

Requirements 1 and 2 together mean the relation is a strict partial order on distinct elements. Requirement 4 is the one that is usually overlooked, and it is what makes “incomparable” an equivalence relation. Its classes are the keys the sort treats as equal, and stability is defined with respect to those classes, not with respect to the objects’ identity.

A three-element counterexample for requirement 4 uses a relation that is a valid strict partial order and still fails: on the set ${1, 2, 3}$ let $1 \prec 2$ and let $3$ be incomparable to both. Then $1$ and $3$ are incomparable, $3$ and $2$ are incomparable, but $1 \prec 2$. The relation is irreflexive, asymmetric, and transitive, so requirements 1 to 3 hold and only requirement 4 fails.

The failure is visible in an output. Feed the array [2, 3, 1] to insertion sort with this relation. The element 3 does not compare less than 2, so it stays where it is; the element 1 does not compare less than 3, so it also stays. The output is [2, 3, 1], and yet $1 \prec 2$, so the result is not sorted. The algorithm did nothing wrong: its correctness argument needs the relation to be a strict weak ordering, and this one is not.

What the sort does with the relation

Merge sort’s merge reads the relation as “take from the left run unless the right is strictly smaller”. That is only coherent if the relation is a total preorder on the key classes. Concretely, the merge relies on: if the left front is not less than the right front, then the right front is not less than the left front either, up to the equivalence class. Asymmetry gives that. And it relies on the output being sorted with respect to all later comparisons, which transitivity gives.

Quicksort’s partition is more fragile. Hoare’s two-index scan advances i while a[i] < pivot and retreats j while a[j] > pivot, then swaps. The termination argument needs both scans to stop before crossing. With two reachable elements $x$ and $y$ for which the comparator reports both $x \prec y$ and $y \prec x$, the forward scan cannot stop on $x$ and the backward scan cannot stop on $y$, so neither index finds a stopping element where it should, and the two indexes cross inside the range. The returned split point then has no relation to where the keys actually lie, the recursion makes no progress, and implementations that rely on the split to shrink the range can read and write outside the partition range. That breaks asymmetry rather than irreflexivity, and it happens when the key function reads a field that mutates during the sort, or when it is derived from a hash of an object identity that changes when objects move. The scheme itself is described in quicksort partition schemes. The C++ standard makes this undefined behaviour, and implementations do not check: a std::sort over a range with an invalid comparator may access elements outside the range, and no diagnostic is required. The failure is not a wrong ordering; it is memory corruption.

The three realistic ways to break it

Comparators in real code fail in a small number of characteristic ways.

Inconsistent comparison of a mutable field. The comparator reads a field that changes between calls, for instance a timestamp updated by another thread, a lazily computed cached value, or a counter. Even single-threaded code can do this if the comparator’s result depends on allocation state.

Non-transitive comparison by subtraction. The classic form is return a - b; on integers, used as a three-way comparator. It behaves correctly until a difference exceeds the range of the type, at which point the subtraction wraps and the sign of the result can contradict the true order. On 32-bit int the difference of two values near the extremes overflows. The fix is to compare with < and > branches, which cannot overflow.

Floating-point comparisons with NaN. IEEE 754 specifies that all comparisons with NaN are false, including NaN < x and NaN > x. A comparator written as a < b ? -1 : (b < a ? 1 : 0) therefore reports NaN as incomparable to everything, which makes incomparability non-transitive as soon as the array holds both NaN and ordinary numbers: NaN is incomparable to 1 and to 2, but 1 and 2 compare. Requirement 4 fails. A sort given such a comparator produces an output that is not sorted with respect to it, and the order in which it leaves the non-NaN elements is left to whatever the partition scheme’s index movement does with a NaN in its path.

The C++ approach for floating-point keys is to define a total order on the bit patterns, which IEEE 754 does specify, and to sort by that. Java’s Double.compare does the same. Both make NaN comparable, placing it above all other values.

The Java case: an explicit contract violation check

Java’s Arrays.sort for objects uses Timsort, and Timsort’s merge logic checks some consequences of the contract instead of corrupting memory silently. When the run-length invariant cannot be repaired, the implementation throws IllegalArgumentException carrying the message that the comparison method violates its general contract.

The detection is not complete; it catches violations that produce an inconsistent run structure, not every possible inconsistency. But the difference in failure mode is instructive. A merge-based sort has explicit invariants over run lengths and element order that can be checked with a few comparisons; a partition-based sort has an implicit invariant over index movement that is much harder to check without doubling the work.

The contract itself is documented in the Comparator interface: the implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y, that the relation is transitive, and that compare(x, y) == 0 implies sgn(compare(x, z)) == sgn(compare(y, z)) for all z. The third condition is the formal statement of requirement 4 combined with consistency of the sign function.

Testing a comparator before trusting it

The contract can be checked directly on a sample. Pick triples and verify transitivity; pick pairs and verify antisymmetry. A randomized check over a few thousand elements catches most real violations, because the violations that matter are usually systematic rather than rare.

import random

def check_order(cmp, data, trials=20000):
    """cmp(a, b) < 0 means a before b. Returns a list of violated properties."""
    bad = []
    for _ in range(trials):
        x, y, z = random.sample(data, 3)
        if cmp(x, x) != 0:
            bad.append(("irreflexive", x))
        if (cmp(x, y) < 0) != (cmp(y, x) > 0):
            bad.append(("antisymmetric", x, y))
        if cmp(x, y) < 0 and cmp(y, z) < 0 and not cmp(x, z) < 0:
            bad.append(("transitive", x, y, z))
        if cmp(x, y) == 0 and cmp(x, z) != cmp(y, z):
            bad.append(("equivalence", x, y, z))
        if len(bad) > 10:
            break
    return bad

The equivalence check compares signs rather than requiring every call to return exactly zero: a three-way comparator may return any negative number for less, so the invariant is that equal keys agree on how they relate to every third key, which is cmp(x, z) != cmp(y, z) and not cmp(x, z) != 0.

Sampling finds violations only if the sample contains the offending combination, so it is a smoke test, not a proof. The systematic cases, namely overflow in subtraction, NaN, and a comparator that reads a field mutated by another thread, are better found by inspection, because each has a known shape.

Why the contract is not checked at runtime

A sort could verify every comparison’s consistency, but the cost is prohibitive: checking transitivity requires remembering previous answers, and the memory for that is comparable to the input. Checking only antisymmetry doubles the number of calls to the comparator, since every pair must be compared in both directions. Libraries therefore leave the precondition to the caller, and the documentation states it in the strongest terms available.

The practical consequence for API design is that a comparator should be a pure function of immutable data. Where the key is expensive to compute, compute it once into a parallel array of keys and sort indices by those keys, which removes the possibility of the key changing mid-sort and usually makes each comparison cheaper. That transformation is also what makes radix sorting of records practical: sort the extracted integer keys, then permute the records by the resulting index order.