[Python-Dev] Stable sort and partial order

Mon Nov 1 14:06:40 CET 2010

On 2010年11月01日 12:33:31 +0100, Antoine Pitrou <solipsis at pitrou.net> wrote:
> On 2010年11月01日 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