Unexpected sorted result

[mwtoews]

Bug report

Bug description:

Python 3.13 breaks the sorted() built-in using a custom class key. Here is some demo code to show it:

class Within:
    def __init__(self, o):
        self.o = o
    def __lt__(self, other):
        print("{}.issubset({}): {}".format(self.o, other.o, self.o.issubset(other.o)))
        return self.o.issubset(other.o)

a = set([1])
b = set([1, 2])
c = set([1, 2, 3])
d = set([4])
actual = sorted([c, a, d, b, c], key=Within)
expected = [a, b, c, c, d]
print("(actual == expected):", actual == expected)

The Within class defines if a set is "within" another via issubset (or <= operator) method in __lt__, which also prints the comparison to show what the sort algorithm is comparing.

Testing with Python 3.3 to Python 3.12 via docker, the expected output is:

{1}.issubset({1, 2, 3}): True
{4}.issubset({1}): False
{4}.issubset({1, 2, 3}): False
{1, 2}.issubset({1, 2, 3}): True
{1, 2}.issubset({1}): False
{1, 2, 3}.issubset({1, 2, 3}): True
{1, 2, 3}.issubset({1, 2}): False
(actual == expected): True

But with Python 3.13.0 to 3.13.2 via docker, the output is unexpected:

{1}.issubset({1, 2, 3}): True
{4}.issubset({1}): False
{1}.issubset({4}): False
{1, 2}.issubset({4}): False
{4}.issubset({1, 2}): False
{1, 2, 3}.issubset({1, 2}): False
{1, 2}.issubset({1, 2, 3}): True
{1, 2, 3}.issubset({1, 2, 3}): True
{1, 2, 3}.issubset({1, 2}): False
{1, 2, 3}.issubset({1, 2, 3}): True
(actual == expected): False

The result ([a, d, b, c, c]) is incorrect and takes longer (more comparison combinations requested). Some of the comparisons are done more than once (e.g. {1, 2, 3}.issubset({1, 2, 3}) and {1, 2, 3}.issubset({1, 2}) each appear twice), but this is perhaps because c appears twice.

The background for this issue is that I discovered it while looking at upgrading doctesting for this shapely manual using Python 3.13.1. The example make a custom class that uses a geospatial "contains" method for __lt__.

CPython versions tested on:

3.13

Operating systems tested on:

Linux

[tomasr8]

Hi! Please see the set docs and specifically this part:

Since sets only define partial ordering (subset relationships), the output of the list.sort() method is undefined for lists of sets.

[mwtoews]

Just to be clear, this is not a bug with set or about ordering with set objects. The <= operator is equivalent to issubset, similar to the geospatial "within" operator. The demo with set objects is to simplify the bug without needing shapely.

[tomasr8]

You don't need the key class at all, this is enough to reproduce it:

on Python 3.12.7

>>> a = set([1])
>>> b = set([1, 2])
>>> c = set([1, 2, 3])
>>> d = set([4])
>>> sorted([c, a, d, b, c])
[{1}, {1, 2}, {1, 2, 3}, {4}, {1, 2, 3}]

on Python 3.13.0

>>> a = set([1])
>>> b = set([1, 2])
>>> c = set([1, 2, 3])
>>> d = set([4])
>>> sorted([c, a, d, b, c])
[{1}, {4}, {1, 2}, {1, 2, 3}, {1, 2, 3}]

As the docs say, the result of sorting a list of sets is undefined so you should not rely on the result. Ideally you should avoid sorting sets altogether.

[mwtoews]

You need the key class to replicate the bug. And I emphasise, this bug is not about sorting sets! Sets are a placeholder for geospatial concepts.

[terryjreedy]

Within is slightly buggy in implementing < as <=. But this will not matter unless sort() calls < on equal objects, which it may not do. The real bug, as Tomas said, is having an expectation on the 'sorted' position of the incomparable set {4}. To me, the 3.13 result of sorting it 'small' is better that the earlier result of sorting it 'big'. The Shapely User Manual has the same bug of expecting any particular result when comparing incomparable polygons. (Why should the 'free-spirited point' be bigger than any polygon?) Report that bug to the authors if you want.

[mwtoews]

Perhaps I was misleading by using <= operator in the example, so I've edited the top issue with issubset. The sort comparisons "bigger" and "smaller" are misleading, as these are set-theory concepts. Here is a Venn-like diagram to show the four sets:

This shows that a is a subset of b, which is a subset of c, and d is disjoint from the other sets.

All Python versions before 3.13 sort these as: [a, b, c, c, d], putting the odd-one out d at the end.

Python 3.13 sorts these as: [a, d, b, c, c], putting d in the middle? Sorting an incompatible d in the middle of a comparable sequence [a, b, c] is nonsense. An obvious alternative would be to expect d at the start.

[mwtoews]

Let me simplify the bug a bit more by not including a duplicate member. For example:

actual = sorted([c, a, d, b], key=Within)
expected = [a, b, c, d]
print("(actual == expected):", actual == expected)

First the expected result with Python 3.12 has the following sorted swap details:

0. Input list to sort: [c, a, d, b]
1. a.issubset(c) is True, swap them: [a, c, d, b]
2. d.issubset(a) is False, no change: [a, c, d, b]
3. d.issubset(c) is False, no change: [a, c, d, b]
4. b.issubset(c) is True, swap them: [a, b, d, c]
5. b.issubset(a) is False, no change: [a, b, d, c]
6. Output: (actual == expected): True

And with the unexpected result with Python 3.13:

0. Input list to sort: [c, a, d, b]
1. a.issubset(c) is True, swap them: [a, c, d, b]
2. d.issubset(a) is False, no change: [a, c, d, b]
3. a.issubset(d) is False, no change: [a, c, d, b]
4. b.issubset(d) is False, no change: [a, c, d, b]
5. d.issubset(b) is False, no change: [a, c, d, b]
6. Output: (actual == expected): False

[tim-one]

The result of sorting is simply not defined if the elements being sorted don't implement a consistent total ordering. Part of which is trichotomy: for any x and y, exactly one of the 3 x < y, x == y, and x > y must be True (and the other two False). Set subset doesn't satisfy that, and nether does polygon containment.

What you got before was purely accidental,. You got the same accidental result for years just because the sorting algorithm didn't change for years. In 3.13 changes were made that can vastly speed sorting a non-increasing run with equal elements. The results on elements of types that don't enjoy a total ordering remain purely accidental, but which accidental results you get may or may not change (depending on the exact inputs). For example, if all the polygons in a list are nested like a collection of Russian dolls, then there is a total ordering among those specific polygons, and sorting will order them smallest to largest.

It would be nice if we could detect "broken" (for sorting) types by magic, but there's no practical way to do that.

[mwtoews]

Using docker snapshots of builds, I've bisected the sorted result change to break since python:3.13.0a6. Bisecting deeper, I found the breaking change from #116578 (bf121d6). I appreciate @tim-one for taking a look at this and providing further details! I can accept "accidental" results to describe pre-3.13.0a6 behaviour. But it would be nice to have some consistency with the disjoint set d to be pushed (in any order) to the end, or beginning (if reverse=True). If this disjoint set is the "broken" item, I suppose it is detected if it always has a False comparison.