Sorting the Reverse Permutation by Prefix Transpositions

Dias and Meidanis present, without a proof, an algorithm to sort the reverse permutation $R_n = [n,n-1,\ldots,1]$ by prefix transpositions. In this report we present a new algorithm based on the previous one and show a complete formal proof of its correctness. From this result we establish a new proved upper bound of $n-\lfloor n/4\rfloor$ for the prefix transposition distance of $R_n$.

2004