Boost C++ Libraries

integer_sort 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).

Some performance plots of runtime vs. n and log2(range) are provided below:

Windows Integer Sort

OSX integer Sort

struct rightshift {
  inline int operator()(DATA_TYPE x, unsigned offset) { return x >> offset; }
};