[Python-Dev] Stable sort and partial order

[Nick Coghlan]

On Tue, Nov 2, 2010 at 2:26 AM, Michael Foord <fuzzyman at voidspace.org.uk> wrote:
> On 01/11/2010 16:23, Nick Coghlan wrote:
>> Looking at assertItemsEqual, I'd be inclined to insert a check that
>> falls back to the "unorderable_list_difference" approach in the case
>> where "expected != sorted(reversed(expected))"
>
> If that is sufficient then it would be a nice way of keeping the fast path.

As far as I can tell, that check is a valid partial ordering detector
for any sequence that contains one or more pairs of items for which
LT, EQ and GE are all False:

>>> seq = [{1}, {2}]
>>> seq[0] < seq[1]
False
>>> seq[0] == seq[1]
False
>>> seq[0] > seq[1]
False
>>> sorted(seq)
[{1}, {2}]
>>> sorted(reversed(sorted(seq)))
[{2}, {1}]

Obviously, if the sequence doesn't contain any such items (e.g. all
subsets of each other), then it will look like a total ordering and
use the fast path. I see that as an upside :)

Cheers,
Nick.

-- 
Nick Coghlan   |   ncoghlan at gmail.com   |   Brisbane, Australia