fastest integer sort implementation for 200-300 bit integers?

Question

What is the fastest integer sort implementation for 200-300 bit sized integers? Exact int size is fixed; I have up to 2 gigabytes with such integers (all in RAM).

I hear that it is possible to sort such set in average at O(n log log M) or even at O(n sqrt(log log M)) time, wher n is number of integers and M is the largest integer. Memory usage is limited (I may use up to 0.5-1 GB addtionally). Sorting can be done in-place; in can be unstable (reorder dups).

Is there C/C++ implementation of such sort method, e.g. of Han & Thorup (2002)?

Answer 1

A Radix Sort can be used to sort data with fixed size keys. As this condition is not often met the technique isn't discussed much, but it can be O(n) when the key size is factored out.