Why does a sort comparator that reports 'equal' for two incomparable items corrupt the result rather than merely ordering them arbitrarily?
answer
- sorting assumes one line
- zero has to mean equal
- equality must chain
- three items, three contradictory verdicts
- any unique tiebreak can close a cycle
basics
~20 sSorting assumes a total order. Reporting 'equal' for incomparable items breaks transitivity, so the comparator contradicts itself: the output can be genuinely unsorted rather than arbitrarily tied, and some sort routines detect the contradiction and fail outright.
solid answer
~50 sA comparator is a claim that the items sit on one line, and a sort routine builds its result by chaining pairwise verdicts it never rechecks. Feed it a partial order with `0` standing for "I cannot tell" and the verdicts stop being consistent: with `a < c` in the order and `b` incomparable to both, the comparator says `a = b`, `b = c` and `a < c`. Equality that is not transitive is not equality, so no arrangement satisfies every verdict at once. What comes back is not "the ties landed in some order" — items that the comparator does relate can end up on the wrong side of each other. A second, quieter failure is **consistency with equality**: a structure that decides membership by the comparator will treat two distinct incomparable items as one and keep only the first.
code
pseudocode · 11 lines# broken: 0 means "I cannot tell", the sort reads it as "the same"
function compare(x, y):
if precedes(x, y): return -1
if precedes(y, x): return +1
return 0
# repaired: rank must satisfy precedes(x, y) => rank(x) < rank(y)
function compareTotal(x, y):
if rank(x) < rank(y): return -1
if rank(x) > rank(y): return +1
return compareKeys(x.id, y.id) # 0 only when the ids matchgo deeper
Remember that a comparator returning zero is claiming the two items are the same, not that you could not decide. Those are different statements.
Walk the three-item contradiction out loud: two equal verdicts plus one strict verdict cannot all hold on a single line, so no output satisfies the comparator.
Demonstrate the diagnosis: contradictory results across runs, a possible abort from the sort itself, and distinct elements vanishing from a collection that compares to decide membership.
The judgment call is where the total order comes from — a maintained monotone rank, a stored sequence, or an explicit decision to expose the partial order and stop pretending items sit on one line.
## What a sort routine is promised A comparison sort never examines all pairs. It performs a small number of comparisons and combines their answers, trusting that the verdicts are mutually consistent. The contract behind that trust is a **total order**: 1. **Totality** — every pair yields a definite before/after/equal verdict. 2. **Transitivity of ordering** — if `a` before `b` and `b` before `c`, then `a` before `c`. 3. **Transitivity of equality** — if the comparator calls `a` and `b` equal, and `b` and `c` equal, it must call `a` and `c` equal. 4. **Antisymmetry of the verdict** — `compare(x, y)` and `compare(y, x)` must report opposite signs. A partial order fails only the first of these. The instinctive patch — return `0` when neither item precedes the other — repairs totality by breaking rule 3, which is much worse. ## The contradiction, concretely Take three items with `a < c` in the underlying order and `b` incomparable to both. | Pair | Comparator says | Because | |---|---|---| | `a`, `b` | equal | neither precedes the other | | `b`, `c` | equal | neither precedes the other | | `a`, `c` | `a` first | the order does relate them | Read as claims about one line: `a` and `b` occupy the same position, `b` and `c` occupy the same position, therefore `a` and `c` occupy the same position — yet the third row insists `a` comes strictly first. No arrangement of three items satisfies all three rows. Whatever the sort returns, it returns something it was told is wrong. ## Two different failures, not one - **A silently wrong permutation.** Because the routine chains verdicts it never rechecks, `c` can be placed before `a` even though the comparator would have objected if asked. The output looks sorted, reads as sorted, and is not. - **A detected abort.** Some sort implementations notice the inconsistency during merging and refuse to continue. Ecosystems differ here: some check, some do not, and some check only for certain input sizes or shapes, so the same comparator can be loud in one environment and silent in another. Relying on the check is not a strategy. Stability does not help either. Stability is a promise about items the comparator calls equal, and it is meaningless when "equal" is not an equivalence in the first place. ## Consistency with equality There is a second obligation beyond sorting. A structure that keeps its elements ordered — a sorted collection that answers membership questions by comparing — treats a `0` verdict as "already present". A comparator that returns `0` for merely incomparable items therefore makes the structure drop or overwrite distinct elements. A comparator is called **consistent with equality** when it returns `0` only for items the domain itself considers the same thing; a comparator built naively from a partial order is not. ## The repair, and the repair that does not work The fix is to supply a genuine total order that **extends** the partial one: whenever the partial order relates a pair, the total order agrees, and it decides every remaining pair as well. The tempting shortcut is to break incomparable pairs with any unique key. It does not work, and the reason is worth tracing. Let `a < c` in the partial order, `b` incomparable to both, and let the keys rank `c` first, then `b`, then `a`. Comparing `a` with `b` falls through to keys and puts `b` first. Comparing `b` with `c` falls through and puts `c` first. But `a` and `c` are related, so `a` comes before `c`. The three verdicts read `c` before `b`, `b` before `a`, `a` before `c` — a cycle, and cycles are not orders. What works is a **monotone rank**: a numeric measure `rank(x)` guaranteed to increase strictly along every related pair, so `x < y` implies `rank(x) < rank(y)`. Ordering by rank first and a unique key second is lexicographic on two total orders, hence itself a total order, and it never contradicts the partial one. The cost is that the rank must be computed and maintained; the benefit is that the comparator now means what the sort assumes it means.
- What does 'consistent with equality' mean for a comparator, and what breaks when it is not?It means the comparator returns `0` only for items the domain calls the same thing. When it is not, any structure that decides membership by comparing — a sorted collection, a deduplicating pass — treats distinct incomparable items as one and keeps only the first. Sorting may look fine while the collection quietly loses elements.
- Does a stable sort rescue an inconsistent comparator?No. Stability only fixes the relative order of items the comparator declares equal. It assumes those declarations are coherent. When equality is not transitive, the routine can already place items on the wrong side of a pair it does relate, and stability says nothing about that.
- What symptom would make you suspect an inconsistent comparator rather than bad data?Sorting the same multiset twice from different starting permutations produces different results that contradict each other on a pair the order does relate. A targeted check helps: sample triples and assert that the verdicts compose — equality chains, and ordering chains.
saying these in an interview costs you the question
- Says an inconsistent comparator only randomises the order of ties
- Claims a stable sort makes the zero-for-incomparable comparator safe
- Believes any unique tiebreak key repairs a partial-order comparator
- Treats a zero verdict as harmless for a collection that deduplicates
- Assumes every sort routine detects a contradictory comparator