On Fri, Dec 11, 2015 at 10:41 PM, Greg Stark <st...@mit.edu> wrote: > > Interestingly it looks like we could raise the threshold to switching > to insertion sort. At least on my machine the insertion sort is faster > in real time as well as fewer comparisons up to 9 elements. It's > actually faster up to 16 elements despite doing more comparisons than > quicksort. > > Note also how our quicksort does more comparisons than the libc > quicksort (which is actually merge sort in glibc I hear) which is > probably due to the "presorted" check.
Heh. And if I comment out the presorted check the breakeven point is *exactly* where the threshold is today at 7 elements -- presumably because Hoare chose it on purpose. 7 using insertion sort 145.517ns per sort of 7 24-byte items 14.9 compares/sort 10.5 swaps/sort using sort networks sort 146.764ns per sort of 7 24-byte items 16.0 compares/sort 7.3 swaps/sort using libc quicksort sort 282.659ns per sort of 7 24-byte items 12.7 compares/sort using qsort_ssup sort 141.817ns per sort of 7 24-byte items 14.3 compares/sort -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers