On Fri, Dec 11, 2015 at 2:41 PM, Greg Stark <st...@mit.edu> wrote: > However the number of comparisons is significantly higher. And in the > non-"abbreviated keys" case where the compare is going to be a > function pointer call the number of comparisons is probably more > important than the actual time spent when benchmarking comparing > int64s. In that case insertion sort does seem to be better than using > the sort networks.
Back when I wrote a prototype of Timsort, pre-abbreviated keys, it required significantly fewer text comparisons [1] in fair and representative cases (i.e. not particularly tickling our quicksort's precheck thing), and yet was significantly slower. [1] http://www.postgresql.org/message-id/caeylb_w++uhrcwprzg9tybvf7sn-c1s9olbabvavpgdep2d...@mail.gmail.com -- Peter Geoghegan -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers