Tim Peters <[EMAIL PROTECTED]> 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 -- http://mail.python.org/mailman/listinfo/python-list
