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)?