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 -- http://mail.python.org/mailman/listinfo/python-list