[Python-Dev] Stable sort and partial order

[R. David Murray]

On Mon, 01 Nov 2010 12:33:31 +0100, Antoine Pitrou <solipsis at pitrou.net> 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 = [{2,4}, {1,2}]
> >  >>> b = 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.  I see no easy way of eliminating the O(n*n)
> issue. Custom key functions can't work in all cases.

Even granting some theoretical way to sort sets by their contents, it
still wouldn't be a bug in sorted.  Sorted is just using the results
returned by '__lt__', which is what it should do.  Special casing sets
in sorted would be wrong.

--
R. David Murray                                      www.bitdance.com