Violation of stable sort criterion

[gempa-stephan]

Bug report

Bug description:

I noticed unexpected sort results since switching to Python 13. My code uses a rather complex comparator function which relies on the stable sort property:

#!/usr/bin/env python3
from functools import cmp_to_key


# Legacy comparison function. Much complexer in orginal code, reduced to mininal
# example here.
def comp(a1, a2):
    # assume tuples are sorted on first element
    if a1[0] != a2[0]:
        return 0

    if a1[1] < a2[1]:
        return -1

    if a1[1] > a2[1]:
        return 1

    return 0


# Data to be sorted, pre-sorted on the first element of each tuple already.
data = [
    ("red", 1),
    ("red", 1.0),
    ("blue", 1.001),
    ("blue", 1),
    ("blue", 1.1),
    ("blue", 1.00),
]

print(data)
print(sorted(data, key=lambda x: x[1]))  # correct result for all Python versions
print(sorted(data, key=cmp_to_key(comp)))  # incorrect result since Python 3.13

# Prints under Python 13
# [('red', 1), ('red', 1.0), ('blue', 1.001), ('blue', 1), ('blue', 1.1), ('blue', 1.0)]
# [('red', 1), ('red', 1.0), ('blue', 1), ('blue', 1.0), ('blue', 1.001), ('blue', 1.1)]
# [('blue', 1), ('red', 1), ('red', 1.0), ('blue', 1.0), ('blue', 1.001), ('blue', 1.1)]

# Prints under Python <13
# [('red', 1), ('red', 1.0), ('blue', 1.001), ('blue', 1), ('blue', 1.1), ('blue', 1.0)]
# [('red', 1), ('red', 1.0), ('blue', 1), ('blue', 1.0), ('blue', 1.001), ('blue', 1.1)]
# [('red', 1), ('red', 1.0), ('blue', 1), ('blue', 1.0), ('blue', 1.001), ('blue', 1.1)]

I couldn't find any notes regarding this changed sort behavior in the changelog.

Regards,
Stephan

CPython versions tested on:

3.13

Operating systems tested on:

No response

[picnixz]

Could this be 8383915 or bf121d6? cc @tim-one

[pochmann3]

Just another case of someone using invalid comparisons.

You say ('blue', 1) < ('blue', 1.001) == ('red', 1), which implies ('blue', 1) < ('red', 1).

[serhiy-storchaka]

Your comparison function violates equality transitivity (if a == b and b == c then a == c).

In particular, ("blue", x) == ("red", y) for any x and y => all ("blue", x) should be equal.