[Python-Dev] Stable sort and partial order

[Antoine Pitrou]

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.

Regards

Antoine.