...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
is a fast templated in-place hybrid radix/comparison algorithm, which in
testing tends to be roughly 50% to 2X faster than std::sort
for large tests (>=100kB). Worst-case performance is 𝑶(N * (log2(range)/s
+ s)), so integer_sort
is asymptotically faster than pure comparison-based algorithms. s
is max_splits, which defaults to 11, so its worst-case
with default settings for 32-bit integers is 𝑶(N * ((32/11)
slow radix-based iterations + 11 fast comparison-based iterations).
integer_sort
Some performance plots of runtime vs. n and log2(range) are provided below:
See rightshiftsample.cpp for a working example of using rightshift, using a user-defined functor:
struct rightshift { inline int operator()(DATA_TYPE x, unsigned offset) { return x >> offset; } };
Other examples:
Sort structs using an integer key.