Re: Using quicksort for every external sort run

On Fri, Dec 11, 2015 at 10:41 PM, Greg Stark <stark(at)mit(dot)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