On Fri, Dec 11, 2015 at 2:41 PM, Greg Stark <stark@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-c1s9oLbABvAvPGdeP2DFSQ@mail.gmail.com
--
Peter Geoghegan