<!-- canonical: efficientnewlanguage.org/ai/examples/219-comparator-not-a-total-order | ai_layer_version: 0.1.0 | updated: 2026-08-03 -->

# Example 219 — Sorted twelve different ways

`comparator_not_a_total_order.eml` sorts one multiset under three comparators, over every permutation of the input, and counts the distinct answers.

## EML

```eml
# Self-authored for the EML case corpus (no external origin). A comparison
# function that is reasonable, useful, and not an ordering.
#
# Sorting needs a comparison that is a TOTAL ORDER. Three laws:
#
#     transitive     a<=b and b<=c  =>  a<=c
#     antisymmetric  a<=b and b<=a  =>  a and b are equivalent
#     total          for any a, b, one of a<=b or b<=a holds
#
# The comparison people actually write when values are noisy is a tolerance:
#
#     "equal if they are within 0.5 of each other"
#
# which is not transitive. 1.0 ~ 1.4 and 1.4 ~ 1.8, but 1.0 and 1.8 are 0.8
# apart and therefore NOT equal. Equality has stopped being an equivalence
# relation, and every sort built on it produces a result that depends on the
# order the elements arrived in.
#
# The failure has no error state. The sort finishes. The output is a list of
# the right length containing the right elements, roughly ascending. Two runs
# over the same multiset in different input orders give different answers, and
# neither is wrong by any check the comparator itself can express.
#
# The measurement here is the definition, made executable: sweep every triple
# and count where transitivity fails, then sort every PERMUTATION of one
# multiset and count the distinct outputs.
#
# The first version of this file expected the repair to give exactly ONE
# output. It gives two, and the reason is the more useful lesson. Quantising
# makes the comparison a total PREORDER, not a total order: ties are real, and
# a stable sort keeps tied elements in whatever order they arrived. So the
# repaired comparator still yields different lists.
#
# What it does yield consistently is the BUCKET SEQUENCE - the run of
# equivalence classes, which is well defined precisely because equality is now
# transitive. That is the property the tolerant comparator cannot offer at any
# price, because it has no equivalence classes to be consistent about.

def cmp_strict(a, b):
    # A genuine total order on floats.
    if a < b:
        return 0 - 1
    if a > b:
        return 1
    return 0

def cmp_tolerant(a, b):
    # "Close enough is equal." Reasonable-sounding; not transitive.
    a - b => d
    if d < 0:
        0 - d => d
    if d <= 0.5:
        return 0
    if a < b:
        return 0 - 1
    return 1

def cmp_rounded(a, b):
    # The repair: quantise ONCE to a grid, then compare exactly. Equality is
    # now "same bucket", which is transitive because bucket membership is.
    int(a * 2 + 0.5) => qa
    int(b * 2 + 0.5) => qb
    if qa < qb:
        return 0 - 1
    if qa > qb:
        return 1
    return 0


def insertion_sort(xs, which):
    [] => out
    for x in xs:
        out + [x] => out
    1 => i
    while i < len(out):
        out[i] => cur
        i - 1 => j
        while j >= 0 and compare(which, out[j], cur) > 0:
            out[j] => out[j + 1]
            j - 1 => j
        cur => out[j + 1]
        i + 1 => i
    return out

def compare(which, a, b):
    if which == "strict":
        return cmp_strict(a, b)
    elif which == "tolerant":
        return cmp_tolerant(a, b)
    return cmp_rounded(a, b)

def render(xs):
    "" => s
    for x in xs:
        if len(s) > 0:
            s + " " => s
        s + str(x) => s
    return s


# Four values, not five: 120 permutations produce a 14 MB execution trace for
# a program whose output is thirty lines. The transitivity break (1.0 ~ 1.4 ~
# 1.8) and a quantisation tie (1.0 with 1.1, both in bucket 2) both survive.
[1.0, 1.1, 1.4, 1.8] => values

"The three values that break transitivity:"^0
("  cmp_tolerant(1.0, 1.4) = " + str(cmp_tolerant(1.0, 1.4)) + "   (equal)")^0
("  cmp_tolerant(1.4, 1.8) = " + str(cmp_tolerant(1.4, 1.8)) + "   (equal)")^0
("  cmp_tolerant(1.0, 1.8) = " + str(cmp_tolerant(1.0, 1.8)) + "  (NOT equal)")^0

# ---------------------------------------------- law 1: transitivity, swept
def transitivity_failures(which):
    0 => bad
    for a in values:
        for b in values:
            for c in values:
                if compare(which, a, b) <= 0 and compare(which, b, c) <= 0:
                    if compare(which, a, c) > 0:
                        bad + 1 => bad
    return bad

""^0
("transitivity failures over " + str(len(values) * len(values) * len(values)) + " triples:")^0
("  strict:   " + str(transitivity_failures("strict")))^0
("  tolerant: " + str(transitivity_failures("tolerant")))^0
("  rounded:  " + str(transitivity_failures("rounded")))^0

# ------------------------------------ law 2: the sort must not depend on order
# Every permutation of the five values, generated by repeated selection.
def permutations(xs):
    if len(xs) <= 1:
        return [xs]
    [] => out
    for i in [0:len(xs) - 1]:
        xs[i] => head
        xs[:i] + xs[i + 1:] => rest
        for p in permutations(rest):
            out + [[head] + p] => out
    return out

permutations(values) => perms

def distinct_results(which):
    {} => seen
    for p in perms:
        render(insertion_sort(p, which)) => r
        if r in seen:
            seen[r] + 1 => seen[r]
        else:
            1 => seen[r]
    return seen

distinct_results("strict") => d_strict
distinct_results("tolerant") => d_tolerant
distinct_results("rounded") => d_rounded

def bucket_seq(xs, which):
    # The sequence of equivalence classes the result walks through. For a
    # comparator with real classes this is invariant; for one without, it is
    # not even well defined.
    "" => s
    for x in xs:
        if which == "rounded":
            str(int(x * 2 + 0.5)) => b
        else:
            str(x) => b
        if len(s) > 0:
            s + "," => s
        s + b => s
    return s

def distinct_buckets(which):
    {} => seen
    for p in perms:
        bucket_seq(insertion_sort(p, which), which) => k
        1 => seen[k]
    return len(seen)

""^0
("permutations sorted:      " + str(len(perms)))^0
("distinct results, strict:   " + str(len(d_strict)))^0
("distinct results, tolerant: " + str(len(d_tolerant)))^0
("distinct results, rounded:  " + str(len(d_rounded)) + "   <- not 1: quantising leaves TIES")^0
""^0
"The same runs, compared by bucket sequence rather than by value:"^0
("  rounded:  " + str(distinct_buckets("rounded")) + "   the equivalence classes are stable")^0
("  tolerant: " + str(distinct_buckets("tolerant")) + "  there are no classes to be stable about")^0

""^0
"Every answer the tolerant comparator gives, and how often:"^0
for r in d_tolerant:
    ("  %-24s %d" % (r, d_tolerant[r]))^0

# ------------------------------------------------- is the output even sorted?
# The trap: each result IS non-decreasing by the comparator that produced it.
# That check cannot see the problem at all.
def is_sorted_by(xs, which):
    for i in [1:len(xs) - 1]:
        if compare(which, xs[i - 1], xs[i]) > 0:
            return False
    return True

0 => tolerant_sorted
for p in perms:
    if is_sorted_by(insertion_sort(p, "tolerant"), "tolerant"):
        tolerant_sorted + 1 => tolerant_sorted

""^0
('results that pass "is it sorted?" by their own comparator: ' + str(tolerant_sorted) + "/" + str(len(perms)))^0
"...which is why the order check is not the check."^0

# ------------------------------------------------------------------ checks
0 => passed
0 => checked

# A real total order gives ONE answer regardless of input order. The repaired
# comparator does NOT - it gives one bucket sequence, which is the strongest
# guarantee available once ties exist. Both halves are asserted, because the
# first version of this file expected the wrong one.
checked + 1 => checked
if len(d_strict) == 1 and len(d_rounded) > 1 and distinct_buckets("rounded") == 1:
    passed + 1 => passed

# The tolerant comparator must give more than one, or nothing is demonstrated.
checked + 1 => checked
if len(d_tolerant) > 1:
    passed + 1 => passed

# It must fail transitivity, and the other two must not.
checked + 1 => checked
if transitivity_failures("tolerant") > 0:
    if transitivity_failures("strict") == 0 and transitivity_failures("rounded") == 0:
        passed + 1 => passed

# And every one of those differing answers must pass an order check - the
# specific reason this survives review.
checked + 1 => checked
if tolerant_sorted == len(perms):
    passed + 1 => passed

# The repair must still DO the job it was written for: values within the
# tolerance land in the same bucket rather than being forced apart.
checked + 1 => checked
if cmp_rounded(1.0, 1.1) == 0 and not (cmp_rounded(1.0, 1.8) == 0):
    passed + 1 => passed

""^0
("checks passed: " + str(passed) + "/" + str(checked))^0
if passed == checked:
    "One multiset, one comparator, twelve answers - all of them 'sorted'." => verdict
else:
    "FAILED - a comparator did not behave as the checks describe." => verdict
verdict^0

""^0
"A tolerance turns equality into a relation that is reflexive and symmetric" => n1
n1^0
"but not transitive, and a sort needs all three. Quantising fixes transitivity" => n2
n2^0
"and does NOT give back a unique answer - ties remain, and a stable sort keeps" => n3
n3^0
"them in arrival order. The guarantee you can actually buy is that the" => n4
n4^0
"equivalence classes are the same every time, which is what makes the result" => n5
n5^0
"reproducible once you also fix the tie order. Expecting one answer from the" => n6
n6^0
"repair was this file's own first premise." => n7
n7^0
```

## Python (deterministic transpilation)

```python
def cmp_strict(a, b):
    if a < b:
        return 0 - 1
    if a > b:
        return 1
    return 0

def cmp_tolerant(a, b):
    d = a - b
    if d < 0:
        d = 0 - d
    if d <= 0.5:
        return 0
    if a < b:
        return 0 - 1
    return 1

def cmp_rounded(a, b):
    qa = int(a * 2 + 0.5)
    qb = int(b * 2 + 0.5)
    if qa < qb:
        return 0 - 1
    if qa > qb:
        return 1
    return 0

def insertion_sort(xs, which):
    out = []
    for x in xs:
        out = out + [x]
    i = 1
    while i < len(out):
        cur = out[i]
        j = i - 1
        while j >= 0 and compare(which, out[j], cur) > 0:
            out[j + 1] = out[j]
            j = j - 1
        out[j + 1] = cur
        i = i + 1
    return out

def compare(which, a, b):
    if which == "strict":
        return cmp_strict(a, b)
    elif which == "tolerant":
        return cmp_tolerant(a, b)
    return cmp_rounded(a, b)

def render(xs):
    s = ""
    for x in xs:
        if len(s) > 0:
            s = s + " "
        s = s + str(x)
    return s

values = [1.0, 1.1, 1.4, 1.8]
print("The three values that break transitivity:")
print("  cmp_tolerant(1.0, 1.4) = " + str(cmp_tolerant(1.0, 1.4)) + "   (equal)")
print("  cmp_tolerant(1.4, 1.8) = " + str(cmp_tolerant(1.4, 1.8)) + "   (equal)")
print("  cmp_tolerant(1.0, 1.8) = " + str(cmp_tolerant(1.0, 1.8)) + "  (NOT equal)")

def transitivity_failures(which):
    bad = 0
    for a in values:
        for b in values:
            for c in values:
                if compare(which, a, b) <= 0 and compare(which, b, c) <= 0:
                    if compare(which, a, c) > 0:
                        bad = bad + 1
    return bad

print("")
print("transitivity failures over " + str(len(values) * len(values) * len(values)) + " triples:")
print("  strict:   " + str(transitivity_failures("strict")))
print("  tolerant: " + str(transitivity_failures("tolerant")))
print("  rounded:  " + str(transitivity_failures("rounded")))

def permutations(xs):
    if len(xs) <= 1:
        return [xs]
    out = []
    for i in range(0, len(xs)):
        head = xs[i]
        rest = xs[:i] + xs[i + 1:]
        for p in permutations(rest):
            out = out + [[head] + p]
    return out

perms = permutations(values)

def distinct_results(which):
    seen = {}
    for p in perms:
        r = render(insertion_sort(p, which))
        if r in seen:
            seen[r] = seen[r] + 1
        else:
            seen[r] = 1
    return seen

d_strict = distinct_results("strict")
d_tolerant = distinct_results("tolerant")
d_rounded = distinct_results("rounded")

def bucket_seq(xs, which):
    s = ""
    for x in xs:
        if which == "rounded":
            b = str(int(x * 2 + 0.5))
        else:
            b = str(x)
        if len(s) > 0:
            s = s + ","
        s = s + b
    return s

def distinct_buckets(which):
    seen = {}
    for p in perms:
        k = bucket_seq(insertion_sort(p, which), which)
        seen[k] = 1
    return len(seen)

print("")
print("permutations sorted:      " + str(len(perms)))
print("distinct results, strict:   " + str(len(d_strict)))
print("distinct results, tolerant: " + str(len(d_tolerant)))
print("distinct results, rounded:  " + str(len(d_rounded)) + "   <- not 1: quantising leaves TIES")
print("")
print("The same runs, compared by bucket sequence rather than by value:")
print("  rounded:  " + str(distinct_buckets("rounded")) + "   the equivalence classes are stable")
print("  tolerant: " + str(distinct_buckets("tolerant")) + "  there are no classes to be stable about")
print("")
print("Every answer the tolerant comparator gives, and how often:")
for r in d_tolerant:
    print("  %-24s %d" % (r, d_tolerant[r]))

def is_sorted_by(xs, which):
    for i in range(1, len(xs)):
        if compare(which, xs[i - 1], xs[i]) > 0:
            return False
    return True

tolerant_sorted = 0
for p in perms:
    if is_sorted_by(insertion_sort(p, "tolerant"), "tolerant"):
        tolerant_sorted = tolerant_sorted + 1
print("")
print("results that pass \"is it sorted?\" by their own comparator: " + str(tolerant_sorted) + "/" + str(len(perms)))
print("...which is why the order check is not the check.")
passed = 0
checked = 0
checked = checked + 1
if len(d_strict) == 1 and len(d_rounded) > 1 and distinct_buckets("rounded") == 1:
    passed = passed + 1
checked = checked + 1
if len(d_tolerant) > 1:
    passed = passed + 1
checked = checked + 1
if transitivity_failures("tolerant") > 0:
    if transitivity_failures("strict") == 0 and transitivity_failures("rounded") == 0:
        passed = passed + 1
checked = checked + 1
if tolerant_sorted == len(perms):
    passed = passed + 1
checked = checked + 1
if cmp_rounded(1.0, 1.1) == 0 and not cmp_rounded(1.0, 1.8) == 0:
    passed = passed + 1
print("")
print("checks passed: " + str(passed) + "/" + str(checked))
if passed == checked:
    verdict = "One multiset, one comparator, twelve answers - all of them 'sorted'."
else:
    verdict = "FAILED - a comparator did not behave as the checks describe."
print(verdict)
print("")
n1 = "A tolerance turns equality into a relation that is reflexive and symmetric"
print(n1)
n2 = "but not transitive, and a sort needs all three. Quantising fixes transitivity"
print(n2)
n3 = "and does NOT give back a unique answer - ties remain, and a stable sort keeps"
print(n3)
n4 = "them in arrival order. The guarantee you can actually buy is that the"
print(n4)
n5 = "equivalence classes are the same every time, which is what makes the result"
print(n5)
n6 = "reproducible once you also fix the tie order. Expecting one answer from the"
print(n6)
n7 = "repair was this file's own first premise."
print(n7)
```

## stdout (executed)

```text
The three values that break transitivity:
  cmp_tolerant(1.0, 1.4) = 0   (equal)
  cmp_tolerant(1.4, 1.8) = 0   (equal)
  cmp_tolerant(1.0, 1.8) = -1  (NOT equal)

transitivity failures over 64 triples:
  strict:   0
  tolerant: 2
  rounded:  0

permutations sorted:      24
distinct results, strict:   1
distinct results, tolerant: 12
distinct results, rounded:  2   <- not 1: quantising leaves TIES

The same runs, compared by bucket sequence rather than by value:
  rounded:  1   the equivalence classes are stable
  tolerant: 12  there are no classes to be stable about

Every answer the tolerant comparator gives, and how often:
  1.0 1.1 1.4 1.8          1
  1.0 1.1 1.8 1.4          3
  1.0 1.4 1.1 1.8          2
  1.0 1.8 1.4 1.1          2
  1.1 1.0 1.4 1.8          1
  1.1 1.0 1.8 1.4          3
  1.1 1.4 1.0 1.8          2
  1.1 1.8 1.4 1.0          2
  1.4 1.0 1.1 1.8          3
  1.4 1.1 1.0 1.8          3
  1.8 1.4 1.0 1.1          1
  1.8 1.4 1.1 1.0          1

results that pass "is it sorted?" by their own comparator: 24/24
...which is why the order check is not the check.

checks passed: 5/5
One multiset, one comparator, twelve answers - all of them 'sorted'.

A tolerance turns equality into a relation that is reflexive and symmetric
but not transitive, and a sort needs all three. Quantising fixes transitivity
and does NOT give back a unique answer - ties remain, and a stable sort keeps
them in arrival order. The guarantee you can actually buy is that the
equivalence classes are the same every time, which is what makes the result
reproducible once you also fix the tie order. Expecting one answer from the
repair was this file's own first premise.
```

## Round-trip

`ok: true` — round-trip fixpoint reached (python1 == python2)

## Trace event types

eml:run:start · eml:def · eml:assign · eml:output · eml:call · eml:return · eml:run:done