Does C++ Algorithm/Boost Lib have Radix Sort?

Question

I want to sort integers and I know radix sort is supposed to be awesome for it. Any library implementation for this sort?

Answer 1

Depends on how strictly you define radix sort, since Boost 1.58.0 includes Spreadsort, which is a hybrid sorting algorithm that heuristically mixes bucket and comparison sorting.

For sorting integers and with no requirement for worst-case Θ(n) efficiency, Spreadsort should satisfy you.

For argument's sake, you can also take a look at my implementation of LSD radix sort, which is fairly inefficient with memory but occasionally faster than Spreadsort. You only require the radix_sort branch but I've linked to the speed_test branch because it has the readme.

Answer 2

The more actual answer is Yes since 1.58 it does:

• http://www.boost.org/doc/libs/1_58_0/libs/sort/doc/html/index.html

It has something known as SpreadSort and will "magically" detect optimized paths for types like std::string, or floating point numbers that can be treated as byte arrays.