[Python-Dev] Stable sort and partial order

[R. David Murray]

On Mon, 01 Nov 2010 14:26:19 -0000, Michael Foord <fuzzyman at voidspace.org.uk> wrote:
> On 01/11/2010 11:33, Antoine Pitrou wrote:
> > On Mon, 01 Nov 2010 02:55:35 +0000
> > Michael Foord<fuzzyman at voidspace.org.uk>  wrote:
> >> Having a more efficient 'slow-path' and moving to that by default would
> >> fix it. The bug is only a duplicate of the bug in sorted - caused by the
> >> fact that sets / frozensets can't be sorted in the standard Python way
> >> (their less than comparison adheres to the set definition). This is
> >> something that will probably surprise many Python developers:
> >>
> >>   >>>  a =3D [{2,4}, {1,2}]
> >>   >>>  b =3D a[::-1]
> >>   >>>  sorted(a)
> >> [set([2, 4]), set([1, 2])]
> >>   >>>  sorted(b)
> >> [set([1, 2]), set([2, 4])]
> >>
> >> (Fixing the bug in sorted would fix assertItemsEqual ;-)
> > How is this a bug? The sort algorithm is stable, which means the above
> > behaviour is a feature.
> 
> Well, bug is the wrong word as it is obviously an intended feature (or
> consequence of a feature). I still think, given the general behaviour of
> Python sorting, that it is unexpected. It breaks what is usually an
> invariant for sorting without an explicit key that sortable types
> sorted(l) = sorted(l[::-1]).

Well, as Antoine pointed out, Python's sorting algorithm is stable,
so that is in fact *not* an invariant:

>>> x = ['abcd', 'foo'*50, 'foo'*50, 'dkke']
>>> y = x[::-1]
>>> [id(n) for n in sorted(x)]
[3073747680, 3073747904, 3073747624, 3073747512]
>>> [id(n) for n in sorted(y)]
[3073747680, 3073747904, 3073747512, 3073747624]

Yes, == usually hides the fact that the *objects* are in a different
order, but obviously that doesn't apply to sets :)

--
R. David Murray                                      www.bitdance.com