3 ms·
> let us begin with a file of a hundred-million totally random integers [...] This is objectively the worst case, containing the greatest possible entropy; but
by ot 5y ago
> let us begin with a file of a hundred-million totally random integers [...] This is objectively the worst case, containing the greatest possible entropy; but also the best case, hiding no surprises.
There is no single worst case for sorting, and in fact most benchmarks use a several different inputs, and even the best algorithms win some and lose some. It's important not to overfit to a specific distribution.
For example, fully random integers can benefit MSB-radix-type sorts, because it's enough to look at a log(n) prefix of the integer to have the data almost sorted, so the later passes have very predictable behavior.
Also the chance of duplicates is negligible, and duplicates are problematic for some quicksort implementations.
- ot 5y agoFor 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.
- ncmncm 5y agoIf you are designing a sorting algorithm component for production, it is critical to take into account all the blips and wrinkles that real components will face. But when you are investigating how and why your CPU has the performance characteristics it has evolved, all those complications directly interfere with learning. The goal here was not to make a production-grade sorting tool; it was to understand what affects performance, using the sorting problem as a microscope. The method is generally useful. Some years back I spent months refining a one-page program[1] to generate a list of word puzzles. After the first day, the list of puzzles was of no interest, but refining the means to produce it faster taught me a great deal. [1] https://github.com/ncm/nytm-spelling-bee https://github.com/ncm/nytm-spelling-bee