Yijie Han, Mikkel Thorup: Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space. FOCS 2002: 135-144