On Compressing Permutations and Adaptive Sorting
Jérémy Barbay and Gonzalo Navarro
We prove that,
given a permutation pi over [1..n] formed of nRuns sorted blocks of
sizes given by the vector R=< r_1,...,r_nRuns>, there exists
a compressed data structure encoding pi in n(1+H(R)) =
n+sum_{i=1}^nRuns r_i log_2 (n/r_i) <= n(1+ log_2 nRuns) bits while
supporting access to the values of pi() and pi^{-1}() in time
O(log nRuns / log log n) in the worst case and
O(H(R) / log log n) on average, when the argument is uniformly
distributed over [1..n]. This data structure can be constructed in time
O(n(1+H(R))), which yields an improved adaptive sorting
algorithm. Similar results on compressed data structures for permutations and
adaptive sorting algorithms are proved for other preorder measures of
practical and theoretical interest.