Sorting documentation claims that sorting algorithm is only using < comparisons
https://docs.python.org/3/howto/sorting.html#odd-and-ends
https://docs.python.org/3/library/stdtypes.html#list.sort

When __lt__ implementation is missing, you get an exception
class Foo:
    pass
sorted([Foo(), Foo(), Foo()])
TypeError: '<' not supported between instances of 'Foo' and 'Foo'

However, if implement __gt__ method, you doesn't get an exception
class Foo:
    def __gt__(self, other):
        return False
sorted([Foo(), Foo(), Foo()])  # ok


Is it supposed to work like this? Or is it lack of documentation?

The `<` comparison uses `__lt__` dunder if it exists, otherwise it falls back on `__gt__`.

To be precise, when doing `a < b`, either `a.__lt__` or `b.__gt__` can be used, since `__gt__` is considered the reversed / reflected version of `__lt__` (analogous to `__add__` and `__radd__`).


>>> class A:
...     def __lt__(self, other): return False
... 
>>> class B:
...     def __gt__(self, other): return True
... 
>>> A() < B()
False
>>> B() < A()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'B' and 'A'
>>> sorted([A(), B()])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'B' and 'A'
>>> sorted([B(), A()])
[<__main__.B object at 0x10dc4cca0>, <__main__.A object at 0x10dc68ca0>]

Presumably in the normal case, all the objects being sorted have the same type, and so in that case it's enough that the type implements at least one of __lt__ and __gt__.

I got your point. So it seems that two pieces of documentation are not equivalent: 

https://docs.python.org/3/howto/sorting.html#odd-and-ends
> The sort routines are guaranteed to use __lt__() when making comparisons between two objects.

https://docs.python.org/3/library/stdtypes.html#list.sort
> This method sorts the list in place, using only < comparisons between items.

Right, the HOWTO language could possibly be improved. The intended and practical message is that you *only* need to provide __lt__ everywhere for sort to work.

It's hard to be clearer without being annoyingly wordy.  The truth is that sort does all comparisons by calling the CAPI:

    PyObject_RichCompareBool(v, w, Py_LT)`

Sorting doesn't know (or care) how `PyObject_RichCompareBool()` is implemented.  The closest Python equivalent is:

    bool(v < w)

although then you also have to be clear that `bool` refers to the builtin function of that name.

Regardless, the sorting docs certainly aren't the place to explain how `v < w` is implemented.  For example, that it _may_ end up calling `w.__gt__(v)` has nothing to do with sorting - instead that's about the semantics of comparison operators, regardless of context.

Since, best I can recall, nobody has asked about this before, perhaps the docs don't need "improvement" ;-)  If they do, then I'm with Mark:  the _intent_ was to say "if you want a class to implement its own sorting order, then it's sufficient to implement `__lt__` alone, and then sorting will use only that comparison operator if the list contains only instances of that class".

On Sun, Jan 05, 2020 at 02:19:49AM +0000, Tim Peters wrote:

> Since, best I can recall, nobody has asked about this before

See discussion here:

https://mail.python.org/archives/list/python-dev@python.org/message/5AQMG6ADD6RGPLI3VTILB2MKXMBFTIGU/

which followed from discussions on sort order. I was asked to provide a 
PR, but I have technical difficulties with github.

I think it's sufficient to say that sorting relies only on the `<` 
operator, and link to the section of the docs that map special dunders 
to comparison operators, namely here:

https://docs.python.org/3/reference/datamodel.html#object.__lt__

where it goes into detail about reflected methods and such.