5 ms·

Just for fun, I added pdqsort to the benchmark: https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort Here are some of the results on an Ivy Bridge

Just for fun, I added pdqsort to the benchmark: https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort Here are some of the results on an Ivy Bridge hackintosh: size, qsort, inline, sort, stable, pdqsort, radix7 1000, 88.0, 60.6, 31.2, 37.5, 24.6, 12.8 10000, 109.3, 77.1, 45.6, 51.6, 29.1, 12.0 100000, 137.1, 97.7, 57.7, 71.9, 33.3, 12.5 1000000, 159.6, 114.2, 70.6, 88.6, 39.7, 20.4 10000000, 185.2, 133.7, 82.0, 99.7, 43.6, 19.4 Edit: it's not quite as easy to plug radix7 into pdqsort's more varied benchmark program, which expects a template function with a type parameter of int.

BeeOnRope 6y ago
Thanks for this! I have a follow-on article to this one with some better radix sort approaches, but I never finished it and it remains unpublished. That one did compare the performance with some other non-standard library sorts, and I'll add prqsort to the list. Admittedly, the benchmark I am using is very simple. In general, radix sort is sensitive to very different characteristics of the input than almost any comparison based sort. E.g., LSD radix sorts (at least like the ones presented here) care about the full range of the input, or how many bits are non-zero in any key (or some similar thing) since the number of passes is related to the number of relevant bits. Similarly, certain patterns that are good for quicksort or merge sort are terrible for radix sort and vice versa. So it's hard to crown an overall winner: it is input dependent.