Faster than radix sort: Kirkpatrick-Reisch sorting

Radix sort sorts n w-bit integers by splitting them up into chunks of log⁡n\log nlogn bits each, and sorting each chunk in linear time. Thus it achieves O(nw/log⁡n)O(nw/\log n)O(nw/logn) time.