Integer Sort

| Home | Libraries | People | FAQ | More

### 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

#### Integer Sort Examples

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.