Sorting (not Python-specific)

[Tim Peters]

[Marcin 'Qrczak' Kowalczyk]
> What are advantages and disadvantages in parametrizing sorting either
> by '<' or by the 3-way comparison?

Primarily cultural, I think:  depending on which one you pick, you'll
confuse either C or Lisp programmers.  Python's internals are in an odd
state now, where for backward compatibility a comparison function passed to
list.sort() must follow the 3-way scheme, but the sorting routine only asks
"less than 0, or not?", i.e. "__lt__, true or false?" is the only comparison
outcome it wants.  And objects that support *only* __lt__ comparison sort
fine by default:

>>> class C:
...     def __init__(self, n):
...         self.n = n
...     def __lt__(x, y):
...         print "asked %d < %d?" % (x.n, y.n)
...         return x.n < y.n
...     def __cmp__(x, y):
...         print "OOPS!"
...
>>> x = map(C, range(10))
>>> import random
>>> random.shuffle(x)
>>> x.sort()
asked 5 < 7?
asked 5 < 7?
asked 2 < 7?
asked 2 < 5?
asked 9 < 5?
asked 9 < 7?
asked 6 < 7?
asked 6 < 5?
asked 8 < 6?
asked 8 < 9?
asked 8 < 7?
asked 0 < 7?
asked 0 < 5?
asked 0 < 2?
asked 3 < 6?
asked 3 < 2?
asked 3 < 5?
asked 4 < 6?
asked 4 < 3?
asked 4 < 5?
asked 1 < 5?
asked 1 < 3?
asked 1 < 2?
asked 1 < 0?
>>>

Note that if huge masses of equal elements are an expected case, you may
*want* to use a 3-way scheme for clarity and efficiency inside the sorting
routine.  Indeed, Python's internal sort does a bit of "OK, it was not the
case that x < y, and also not the case that y < x, therefore if this
ordering is sane for sorting at all, it must be the case both that x >= y
and y >= x, so that x == y" deduction.  But there's *just& "a bit" of that,
and using equality-testing too wouldn't speed it up.

if-equality-is-a-slippery-concept-then-so-is-inequality-ly y'rs  - tim