Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

PrevUpHomeNext
Integer Sort

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

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.

Sort integers in reverse order.

Simple sorting of integers; this case is a performance test for integers that are already mostly sorted.


PrevUpHomeNext