3 ms·
For example, the radix sort implementation is cheating here: for (auto& v : buckets) v.reserve((end - begin)/128); It's assuming uniform distribution of t
by ot 5y ago
For example, the radix sort implementation is cheating here:
for (auto& v : buckets) v.reserve((end - begin)/128);
It's assuming uniform distribution of the buckets, so it can make a very accurate guess and avoid extra allocations. If that line is removed for the general case, I would expect things to get a lot slower.
I would be curious to see a comparison with a good implementation of in-place radix sort. For example there is one available in boost.
- dragontamer 5y agoThe radix sort isn't really the crux of the article. They're trying to just see how fast radix sort is ("unfairly"), and then try to improve a different comparison-sort instead.
- ncmncm 5y agoExactly. Quicksort, also, isn't the crux of the article. Both are ways to sample how the CPU behaves. That is why the quicksort is also not production-grade. If it were more complicated, it would teach us less.