Introduction

Sorting algorithms do not merely need a function that compares two values. They need a comparator that obeys a contract. If that contract is broken, the algorithm may still run, but the result is no longer meaningfully "sorted," and standard correctness proofs stop applying.

What a Valid Comparator Must Guarantee

Most sorting APIs assume an ordering with three core properties:

• If two values are equal, the comparator reports equality.
• If a comes before b, then b must not come before a.
• If a comes before b and b comes before c, then a must come before c.

The last rule, transitivity, is the one that usually breaks buggy comparators. Once that happens, the algorithm is asked to arrange items into an order that does not really exist.

A Comparator Can Create Cycles

Here is a small Python example that defines a cyclic order. It claims that rock comes before paper, paper comes before scissors, and scissors comes before rock.

1from functools import cmp_to_key
2
3def bad_compare(a, b):
4    if a == b:
5        return 0
6
7    beats = {
8        ("rock", "paper"),
9        ("paper", "scissors"),
10        ("scissors", "rock"),
11    }
12
13    return -1 if (a, b) in beats else 1
14
15data = ["rock", "paper", "scissors"]
16result = sorted(data, key=cmp_to_key(bad_compare))
17print(result)

This code runs, but the comparator is inconsistent. There is no global ordering that satisfies all three pairwise claims at once. Any output the sort returns is therefore suspect, because another comparison later in the same run can contradict the earlier one.

What This Means for Algorithm Analysis

Textbook analysis of quicksort, mergesort, heapsort, and similar algorithms assumes the comparator defines a valid order. Under that assumption, we can reason about correctness and comparison counts.

With a broken comparator, two things change:

First, correctness is undefined. The output may fail a later sortedness check, or it may look sorted for some adjacent pairs while still violating the comparator elsewhere.

Second, asymptotic analysis becomes much less useful. A particular implementation may still make about O(n log n) comparison calls, but that tells you little when the comparator gives contradictory answers. In some libraries the sort may terminate with arbitrary output. In others it may detect the violation and raise an error. Java's sorting code is known to throw an exception in some comparator-contract violations, while C++ standard sorting requires a strict weak ordering and otherwise enters undefined behavior.

How to Diagnose the Problem

If you suspect a comparator is wrong, test the contract directly on a sample of values. A quick sanity check often finds the bug faster than staring at the sort implementation.

1def is_transitive(values, cmp):
2    for a in values:
3        for b in values:
4            for c in values:
5                if cmp(a, b) < 0 and cmp(b, c) < 0 and not cmp(a, c) < 0:
6                    return False, (a, b, c)
7    return True, None
8
9ok, witness = is_transitive(["rock", "paper", "scissors"], bad_compare)
10print(ok, witness)

That kind of helper is simple, but it makes the failure concrete by showing one triple that violates transitivity.

Write Comparators from Stable Keys When Possible

The safest comparator is often no custom comparator at all. If you can derive a stable sort key, use that key directly. For example, sort people by last name and then first name instead of manually writing deeply nested compare logic.

When you do need a comparator, keep it deterministic and based only on immutable data. Comparators that inspect global state, current time, random numbers, or mutable containers are common sources of "impossible" sorting bugs.

Common Pitfalls

One frequent mistake is returning inconsistent results for ties. If two records are equal on the primary field, the comparator must handle the next field consistently rather than sometimes returning less-than and sometimes greater-than.

Another pitfall is using subtraction to compare large integers in languages where overflow is possible. A safe comparison should test ordering directly instead of relying on arithmetic differences.

Mutable external state is another danger. If the comparator reads a value that changes during sorting, the same pair of items can produce different answers at different times.

Summary

• Sorting algorithms assume the comparator defines a valid ordering.
• If the comparator violates antisymmetry or transitivity, the output is not trustworthy.
• Standard complexity guarantees are no longer meaningful without comparator correctness.
• Library behavior varies: some runtimes throw, others return arbitrary output, and some enter undefined behavior.
• When possible, sort by stable keys instead of writing complicated custom comparator logic.