On compressing permutations and adaptive sorting

We prove that, given a permutation π   over [1..n][1..n] formed of nRuns sorted blocks of sizes given by the vector R=〈r1,…,rnRuns〉R=〈r1,…,rnRuns〉, there exists a compressed data structure encoding π   in n(1+H(R))=n+∑i=1nRunsrilog2nri⩽n(1+log2nRuns) bits while supporting access to the values of π()π() and π−1()π−1() in time O(lognRuns/loglogn) in the worst case and O(H(R)/loglogn) on average, when the argument is uniformly distributed over [1..n][1..n]. This data structure can be constructed in time O(n(1+H(R)))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.