Faster algorithms for sorting by transpositions and sorting by block interchanges

Abstract

In this article, we present a new data structure, called the permutation tree, to improve the running time of sorting permutation by transpositions and sorting permutation by block interchanges. The existing 1.5-approximation algorithm for sorting permutation by transpositions has time complexity O ( n 3/2 √ logn ). By means of the permutation tree, we can improve this algorithm to achieve time complexity O ( nlogn ). We can also improve the algorithm for sorting permutation by block interchanges to take its time complexity from O ( n 2 ) down to O ( nlogn ).