###
LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations

####
Jérémy Barbay, Johannes Fischer, and Gonzalo Navarro

LRM-Trees are an elegant way to partition a sequence of values into
sorted consecutive blocks. They have been used to encode ordinal
trees and to index integer arrays in order to support range minimum
queries on them. We describe how they yield many other convenient
results in a variety of areas: compressed indices for range minimum
queries on partially sorted arrays, a new adaptive sorting
algorithm, and a compressed data structure for permutations
supporting direct and inverse application in time inversely
proportional to the compressibility of the permutation.