On: Hoare’s Rebuttal and Bubble Sort’s Comeback

[gerbenst]

For more clarification. The number 0, 1 in these benchmarks mean the level of indirection. IndirectionSort<0, xxx> is sorting pointers on their address. While IndirectionSort<1, xxx> is sorting pointers on the value it's pointing to. Notice how MergeSort regresses much more then the QuickSort. Without an indirection MergeSort is competitive with an indirection QuickSort becomes relatively much better. As you point out sorting pointers to structs is much more important use case. This property becomes even more important as L1 cache is typically kind of small O(32kb), while L2/L3 cache is large O(1mb). So when sorting pointers it's not unreasonable to hit L2/L3 cache but miss L1. With L2/L3 typically being 10-20 cycles latency (vs 5 cycle for L1) QuickSort is largely insensitive to the L1 cache misses.

    BM_IndirectionSort<1, std_sort>                       93 ns         93 ns    7700000
    BM_IndirectionSort<1, std_stable_sort>               126 ns        125 ns    5600000
    BM_IndirectionSort<1, std_heap_sort>                 172 ns        172 ns    4200000
    BM_IndirectionSort<1, exp_gerbens::QuickSort>         34 ns         34 ns   19000000
    BM_IndirectionSort<1, HeapSort>                      157 ns        157 ns    4700000
    BM_IndirectionMergeSort<1>                            68 ns         68 ns   10400000
    BM_IndirectionSort<0, std_sort>                       74 ns         74 ns    9500000
    BM_IndirectionSort<0, std_stable_sort>                91 ns         91 ns    7800000
    BM_IndirectionSort<0, std_heap_sort>                 125 ns        125 ns    5800000
    BM_IndirectionSort<0, exp_gerbens::QuickSort>         26 ns         26 ns   27200000
    BM_IndirectionSort<0, HeapSort>                       77 ns         77 ns    9300000
    BM_IndirectionMergeSort<0>                            36 ns         36 ns   19400000