A tight upper bound on the number of cyclically adjacent transpositions to sort a permutation

• Upper bound on number of cyclically adjacent transpositions needed to sort a permutation of length n   of ⌊n24⌋.
• This upper bound matches the known lower bound.
• Answers open question in Feng, Chitturi and Sudborough [4].
• Relevant quantity in the design of interconnection networks, and the evolutionary history of the genome.

We consider the problem of upper bounding the number of cyclically adjacent transpositions needed to sort a permutation. It is well known that any permutation can be sorted using at most n(n−1)2 adjacent transpositions. We show that, if we allow all adjacent transpositions, as well as the transposition that interchanges the element in position 1 with the element in the last position, then the number of transpositions needed is at most ⌊n24⌋.