On Adaptive Integer Sorting
Anna Pagh, Rasmus Pagh, and Mikkel Thorup
In Proc. 12th Annual European Symposium on Algorithms, ESA 2004.
Abstract
This paper considers integer sorting on a
RAM. We show that adaptive sorting of a sequence with qn inversions is
asymptotically equivalent to multisorting groups of at most
q keys, and a total of n keys. Using the recent
O(n sqrt(loglog n)) expected time sorting of Han and Thorup on
each set, we immediately get an adaptive expected sorting time of
O(n sqrt(loglog q)). Interestingly, for any positive constant
e, we show that multisorting and adaptive inversion sorting can
be performed in linear time if q<= 2^(log n)^(1-e). We also show how to asymptotically improve the running time of
any traditional sorting
algorithm on a class of inputs much broader
than those with few inversions.