Sorting [was Re: Performance of int/long in Python 3]

[Steven D'Aprano]

On Wed, 03 Apr 2013 07:52:42 -0400, Dave Angel wrote:

> I thought that the sort algorithm used a hash of all
> the items to be sorted, and only reverted to a raw comparison of the
> original values when the hash collided.  Is that not the case?  Or is
> the code you post here only used when the hash collides?

Sorting does not require that the elements being sorted are hashable. 

If I have understood the implementation here:

http://hg.python.org/releasing/3.3.1/file/2ab2a09901f9/Objects/listobject.c

sorting in Python only requires that objects implement the less-than 
comparison.

py> class Funny:
...     def __init__(self, x):
...             self.x = x
...     def __lt__(self, other):
...             return self.x < other.x
...     def __gt__(self, x):
...             raise AttributeError
...     __le__ = __ge__ = __eq__ = __ne__ = __gt__
...
py> L = [Funny(i) for i in range(10)]
py> random.shuffle(L)
py> [f.x for f in L]
[8, 5, 7, 0, 9, 2, 3, 6, 1, 4]
py> [f.x for f in sorted(L)]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]


but if I change Funny.__lt__ to also raise, sorting fails.

I seem to recall that "sort relies only on < operator" is a language 
promise, but I can't seem to find it documented anywhere official.




-- 
Steven