On Tue, Sep 13, 2016, at 13:24, Nikolaus Rath wrote: > On Sep 11 2016, Terry Reedy <tjre...@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. _______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
