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

Nikolaus Rath Nikolaus at rath.org
Thu Sep 15 13:42:50 EDT 2016

On Sep 13 2016, Tim Peters <tim.peters at gmail.com> wrote:

[Terry Reedy <tjreedy at udel.edu>]

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. [Nikolaus Rath <Nikolaus at rath.org>] 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)? It has little to do with architecture, but much to do with the relative cost of comparisons versus pointer-copying. Near the end of https://github.com/python/cpython/blob/master/Objects/listsort.txt [...]

Ah, that makes sense, thanks!

Best, -Nikolaus

-- GPG encrypted emails preferred. Key id: 0xD113FCAC3C4E599F Fingerprint: ED31 791B 2C5C 1613 AF38 8B8A D113 FCAC 3C4E 599F

         »Time flies like an arrow, fruit flies like a Banana.«

More information about the Python-Dev mailing list