###
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.