[Python-Dev] Re: Re: lists v. tuples

[Tim Peters]

>> Then it's answering true to both
>>
>>     x < y ?
>> and
>>     y < x ?
>>
>> The comparison function is insane, then

[Greg Ewing]
> No, I'm the one that's insane, I think. You're right,
> this is impossible.

For a sane comparison function, yes.  Python can't enforce that
user-supplied functions are sane, though, and-- as always --it's Python's
job to ensure that nothing catastrophic happens when users go bad.  One of
the reasons Python had to grow its own sort implementation is that various
platform qsort() implementations weren't robust against ill-behaved cmp
functions.  For example, a typical quicksort partitioning phase searches
right for the next element >= key, and left for the next <= key.  Some are
tempted to save inner-loop index comparisons by ensuring that the leftmost
slice element is <= key, and the rightmost >= key, before partitioning
begins.  Then the left and right inner searches are "guaranteed" not to go
too far, and by element comparisons alone.  But if the comparison function
is inconsistent, that can lead to the inner loops reading outside the slice
bounds, and so cause segfaults.

Python's post-platform-qsort sorts all protect against that kind of crud,
but can't give a useful specification of the result in such cases (beyond
that the list is *some* permutation of its input state -- no element is lost
or duplicated -- and guaranteeing just that much in the worst cases causes
some pain in the implementation).