[Python-Dev] Re: Re: lists v. tuples (original) (raw)

Tim Peters tim_one@email.msn.com
Tue, 15 Apr 2003 23:12:51 -0400

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).