The 2-approximation algorithm for sorting by prefix transposition revisited

A transposition is an operation that exchanges two adjacent blocks in a permutation. A prefix transposition always moves a prefix of the permutation to another location. In this article, we use a data structure, called the permutation tree, to improve the running time of the best known approximation algorithm (with approximation ratio 2) for sorting a permutation by prefix transpositions. By using the permutation tree, we improve the running time of the 2-approximation algorithm to O(n log n).