[Python-Dev] Stable sort and partial order

[R. David Murray]

On Mon, 01 Nov 2010 15:14:36 -0000, Michael Foord <fuzzyman at voidspace.org.uk> wrote:
> On 01/11/2010 15:10, R. David Murray wrote:
> > On Mon, 01 Nov 2010 14:26:19 -0000, Michael Foord<fuzzyman at voidspace.org.uk>  wrote:
> >> 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 :)
> >
> 
> Sorry, that should have been sorted(l) == sorted(l[::-1]) - which *is* 
> the case for your example above.

Yes, I know that's what you meant, that's why I said "== usually hides
this".  If you are restricting yourself to built in types, then your
invariant is mostly true but (IMO) misleading, as set demonstrates.
And it certainly doesn't have to be true for custom types, even if they
don't redefine __lt__.  You can argue that in a good design it should
be, but as the set example indicates, there are problem domains where it
is useful for it not to be.

Or, to put it another way, *if* there is a bug here it would be in set,
not sorted.

--
R. David Murray                                      www.bitdance.com