Blasting past fusion trees

Arne Andersson, Stefan Nilsson, and Torben Hagerup

We present an O(n log log n) worst-case time algorithm for sorting arbitrary integers, a significant improvement over the bound achieved by the fusion tree of Fredman and Willard.