sorting with expensive compares?
aleax at mail.comcast.net
Sat Dec 24 07:12:45 CET 2005
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.
More information about the Python-list