https://www.youtube.com/watch?v=zqs87a_7zxwIt is well known that sorting algorithms can be no faster than O(n log n). Except that for sorting integers, there is a sorting algorithm that can sort in O(n): Radix sort.
In this presentation I will explain how to generalize radix sort so that it can sort almost everything that std::sort can sort. I will also present an optimization to the inner loop of radix sort which makes this more than two times faster than std::sort for many inputs.
The interface for radix sort has to be slightly different than for comparison based sorting, so I will also go over how to make your old use case run with the new algorithm.
