Home Original page

[Python-Dev] Drastically improving list.sort() for lists of strings/ints

Random832 random832 at fastmail.com
Tue Sep 13 13:35:10 EDT 2016 
On Tue, Sep 13, 2016, at 13:24, Nikolaus Rath wrote:
> On Sep 11 2016, Terry Reedy <tjreedy at udel.edu> wrote:
> > Tim Peters investigated and empirically determined that an
> > O(n*n) binary insort, as he optimized it on real machines, is faster
> > than O(n*logn) sorting for up to around 64 items.
> 
> Out of curiosity: is this test repeated periodically on different
> architectures? Or could it be that it only ever was true 10 years ago on
> Tim's Power Mac G5 (or whatever he used)?

Binary insertion sort is still O(n*logn) in comparisons, so it's likely
that this is due to short memmoves being sufficiently fast due to cache
effects as not to matter. The number might have gotten larger or
smaller, though. I wonder if it's something that could be tuned
dynamically, at compile time or install time.
More information about the Python-Dev mailing list