What does python 2.7 use to sort vanilla class instances? I'm interested in the default sorting behavior.
Suppose I have the class
class S():
pass
Then I can create a couple of instances, and sort them:
a = S(); b = S(); c = S()
l = [(a,'a'), (b,'b') ,(c, 'c')]
sorted(l)
This will print some sorting of the objects. Now I have a two part question:
__hash__(), and thus their id()? __hash__() to influence the sorting behavior?Python 3's built-in sorting makes use of the __lt__ method in your class.
The rich comparison methods are special in Python, since they can return a special NotImplemented type if there is not __lt__ defined - take a look at the docs on this page: http://docs.python.org/reference/datamodel.html#the-standard-type-hierarchy
Since the truth value of NotImplemented is True, any boolean comparison that gets NotImplemented will continue as if the first element actually is less than the second, which will cause the sort to leave the list in the same order as it was.
Take a look at the interactive shell. You can see how the truth values would be used in a sort, and that Python thinks that both objects are less than each other:
>>> class S():
... pass
...
>>> a = S()
>>> b = S()
>>> a.__lt__( b )
NotImplemented
>>> if a.__lt__( b ):
... print( "derp!" )
...
derp
>>> if b.__lt__(a):
... print( "derp" )
...
derp
Here are some more references:
EDIT:
After taking a look at Python 2.7, it looks like the ID of the objects is used for sorting, and the __lt__ method is undefined on a simple class like your example. Sorry for any confusion.
[b, c, a].
(value, object) tuples to sort lists is very dangerous if python does a secondary sort on the object's id! I didn't know these kind of things had changed between python versions, I'm indeed using 2.x.Python's sort algorithm exclusively compares items using a "less than" test, which can be implemented either using the __cmp__() special method (now deprecated) or __lt__() on the class.
In the absence of any specific instruction on how to compare two objects, the id() is used (not the hash) for objects of the same type, as in your case.
I tried your example on my own machine (python 2.7):
>>> sorted(l)
[(<__main__.S instance at 0x107142a70>, 'a'), (<__main__.S instance at 0x107142ab8>, 'b'), (<__main__.S instance at 0x107142b00>, 'c')]
Note that the sorted list is in order of the id():
>>> id(a)
4413729392
>>> id(b)
4413729464
>>> id(c)
4413729536
If I generate the hashes I get:
>>> hash(a)
275858087
>>> hash(b)
-9223372036578917717
>>> hash(c)
275858096
Which suggests that the sorting is not based on the hash.
See derekerdmann's answer for information on how to make python sort your class the way you want.
Edit: By the way, if you put the items in the list in reverse and then sort it, you get:
>>> l = [(c,'c'), (b, 'b'), (a, 'a')]
>>> sorted(l)
[(<__main__.S instance at 0x107142a70>, 'a'), (<__main__.S instance at 0x107142ab8>, 'b'), (<__main__.S instance at 0x107142b00>, 'c')]
Once again, its sorted in order of the id().
