  We initiate the study of sorting permutations using prefix
block-interchanges, which exchange any prefix of a permutation with another
non-intersecting interval. The goal is to transform a given permutation into
the identity permutation using as few such operations as possible. We give a
2-approximation algorithm for this problem, show how to obtain improved lower
and upper bounds on the corresponding distance, and determine the largest
possible value for that distance.

Data Structures and Algorithms