sorting with expensive compares?

[Alex Martelli]

Tim Peters <tim.peters at gmail.com> wrote:

> [Steven D'Aprano]
> > ...
> > As others have pointed out, Python's sort never compares the same objects
> > more than once.
> 
> Others have pointed it out, and it's getting repeated now, but it's
> not true.  Since I wrote Python's sorting implementation, it's
> conceivable that I'm not just making this up ;-)
   ...
> could possibly save in general.  It's true that the workhorse binary
> insertion and merge sorts never compare the same elements more than
> once, but there is some potential duplication between those and
> comparisons done to identify natural runs.

Since I probably was the first one to point out the erroneous factoid in
question, I apologize -- obviously, my memories of the inner workings of
sort were faulty, and didn't consider that potential duplication.

In this case, the tricks I already (though dubiously;-) suggested in
order to avoid any avoidable comparisons might pay for themselves and
then some, if comparisons are indeed extremely costly.


Alex