Testing a comparator before trusting a sort

A sorting algorithm relies on its comparator describing a consistent order. If the comparator says rock precedes scissors, scissors precedes paper, and paper precedes rock, no linear sequence can satisfy all three relationships. For a developer debugging inconsistent sort results, testing the comparator can reveal a problem that changing sorting algorithms cannot fix.

A three-way comparator returns a negative value when its first argument should precede its second, zero when their keys are equivalent for sorting, and a positive value when it should follow. The magnitude of a nonzero result is irrelevant; its sign carries the ordering decision. A comparison function must give consistent answers throughout one sort.

Construct a cycle that looks reasonable locally

Rock-paper-scissors describes a tournament relationship, not a sortable ranking. Use the cycle rock before scissors, scissors before paper, paper before rock. Each pair has a winner, but the relation is not transitive.

from functools import cmp_to_key

before = {('rock', 'scissors'), ('scissors', 'paper'), ('paper', 'rock')}


def cyclic_compare(a, b):
    if a == b:
        return 0
    return -1 if (a, b) in before else 1


ordered = sorted(['rock', 'scissors', 'paper'], key=cmp_to_key(cyclic_compare))
assert all(cyclic_compare(ordered[i], ordered[i + 1]) <= 0
           for i in range(len(ordered) - 1))
assert any(cyclic_compare(ordered[i], ordered[j]) > 0
           for i in range(len(ordered)) for j in range(i + 1, len(ordered)))

The first assertion checks adjacent pairs. It can pass even though an earlier element is ordered after a later, nonadjacent element by the same comparator. Under a transitive order, adjacent sortedness implies pairwise sortedness; the cycle removes that implication.

The exact sequence a library produces for an invalid comparator is not a portable contract. The example demonstrates a contradiction in the requested relation. It should not be used to depend on a particular result from a particular sorting implementation. Python’s comparison-function documentation explains cmp_to_key, which adapts a comparator but does not repair its logic.

View full-size image ↗

A consistent ranking needs a separate rule, such as a numeric score, an explicit category priority, or an agreed tie group. The fact that every pair can be compared does not mean those comparisons collectively define an order.

Audit the comparison laws on a small domain

A value should compare equal to itself. Reversing the arguments should reverse the sign. If A precedes B and B precedes C, A must precede C. Values that compare equal should also have the same ordering relation to any third value; otherwise replacing one equivalent key with another could change the result.

from itertools import product


def sign(number):
    return (number > 0) - (number < 0)


def audit_comparator(values, compare):
    values = tuple(values)
    failures = []
    for a in values:
        if compare(a, a) != 0:
            failures.append(('self', a))
    for a, b in product(values, repeat=2):
        if sign(compare(a, b)) != -sign(compare(b, a)):
            failures.append(('reversed-sign', a, b))
    for a, b, c in product(values, repeat=3):
        if compare(a, b) < 0 and compare(b, c) < 0 and compare(a, c) >= 0:
            failures.append(('transitivity', a, b, c))
        if compare(a, b) == 0 and sign(compare(a, c)) != sign(compare(b, c)):
            failures.append(('equivalent-keys', a, b, c))
    return failures

failures = audit_comparator(['rock', 'scissors', 'paper'], cyclic_compare)
assert sum(failure[0] == 'transitivity' for failure in failures) == 3
assert audit_comparator([-2, 0, 4], lambda a, b: (a > b) - (a < b)) == []
assert audit_comparator(iter(['rock', 'scissors', 'paper']), cyclic_compare) == failures

The audit captures the finite domain in a tuple once before the repeated checks. This supports one-use iterators and keeps O(k) references to the supplied values; it does not make deep copies of their contents. An infinite input is outside the contract because materializing it would not finish.

This test costs O(k³) comparator calls for a domain of size k, so it is intended for a small representative set or an exhaustive finite category domain. It does not prove a comparator over arbitrary records correct, but a failing triple is a concrete counterexample you can preserve as a regression test.

The audit assumes the comparator returns ordinary finite numeric results. NaN does not have a meaningful negative, zero, or positive sign under these checks and should be rejected separately. The comparator must also be pure enough that repeated calls with unchanged arguments return the same answer; an audit that observes only one call sequence cannot establish that property universally.

Prefer explicit keys when the order has components

For records ordered by priority, then timestamp, then identifier, a tuple key expresses the hierarchy directly. It also computes expensive derived fields once per record when the sorting API caches keys, as Python’s sorting functions do. Hand-written nested comparison branches can accidentally omit a tie case or reverse one field’s direction.

Missing values need a position policy. A key such as (value is None, value if value is not None else 0) puts missing numeric values last while keeping finite numeric values in order. Floating-point NaNs need their own handling because they are not None and do not follow ordinary numeric comparison laws. Define whether the application rejects them, groups them, or treats them as missing.

Do not use a comparator that reads a changing external score during sorting. If two calls see different scores, even individually sensible comparisons can contradict one another. Snapshot the sorting key before starting the operation, or synchronize the data according to the application’s consistency requirements.

Stability cannot fix a contradictory relation

A stable sort preserves input order for keys that compare equivalent. It still requires the comparator’s equivalence groups and ordering between them to be coherent. The cyclic example has no equal distinct categories, so a stability guarantee has nothing to preserve that would resolve the cycle.

JavaScript also requires a well-formed comparator. MDN’s discussion shows that malformed comparisons can produce different results across engines. Returning only 1 or 0 for an ascending comparison is a common example because swapping the arguments does not reliably reverse the sign.

Test ties with different record identities, each optional field, and extreme numeric values. For bounded category sets, inspect every triple. When a counterexample appears, decide the intended ranking rule before changing code. A sort can arrange a coherent order efficiently; it cannot choose a coherent policy on the application’s behalf.

A tolerance can break the meaning of equality

A comparator can fail even without the rock-paper-scissors pattern. Suppose it treats any two measurements within one unit as equal. Zero is close to 0.75, and 0.75 is close to 1.5, but zero is not close to 1.5. Pairwise closeness does not partition measurements into consistent equivalence groups.

def tolerance_compare(a, b):
    if abs(a - b) <= 1:
        return 0
    return (a > b) - (a < b)

measurements = [0.0, 0.75, 1.5]
assert tolerance_compare(0.0, 0.75) == 0
assert tolerance_compare(0.75, 1.5) == 0
assert tolerance_compare(0.0, 1.5) < 0
failures = audit_comparator(measurements, tolerance_compare)
assert any(failure[0] == 'equivalent-keys' for failure in failures)

The first and second measurements claim to be interchangeable for sorting, yet their relationships to the third differ. Zero must precede 1.5, while 0.75 claims to tie with it. A stable sort cannot infer which of those contradictory requests should take priority. Increasing or decreasing the tolerance does not generally remove the problem; overlapping neighborhoods can still form this pattern.

View full-size image ↗

If the product actually wants fixed measurement bands, define those bands directly. For finite numeric values, flooring gives intervals [k, k + 1) labeled by the integer k. All values with the same band key then have the same relationship to every other band. Python’s math.floor returns the largest integer no greater than the input, including for negative values.

from math import floor


def band_compare(a, b):
    ka, kb = floor(a), floor(b)
    return (ka > kb) - (ka < kb)

assert audit_comparator(measurements, band_compare) == []
assert sorted([1.5, 0.75, 0.0], key=floor) == [0.75, 0.0, 1.5]
assert floor(-0.1) == -1
assert floor(0.99) != floor(1.01)

The zero and 0.75 records keep their input order because the band key ties; the result is ordered by bands, not necessarily by the original measurements within a band. The last assertion exposes the tradeoff: two values only 0.02 apart can fall into different bands on opposite sides of a boundary. Fixed bands are a coherent policy, but they do not implement pairwise “within one unit” grouping.

A display might instead sort by the original numeric value and round only the visible label. Two rows can show the same rounded label while retaining a deterministic underlying order. Whether that is acceptable is a presentation decision, separate from the comparator’s mathematical consistency. Choose it explicitly rather than embedding an approximate-equality rule inside the sort.

For an exercise, test negative values around a band boundary and records that share a band but have different identities. Verify the band comparator’s laws over that small domain, then confirm the stable key sort preserves identity order within each band. Keep nonfinite-value rejection or placement separate: neither tolerance comparisons nor flooring provides an application policy for NaN by itself.