A k-bounded (k ≥ 2) transposition is an operation that switches two elements that have at most k − 2 elements in between. We study the problem of sorting a circular permutation $π$ of length n for k = 2, i.e., adjacent swaps and k = 3, i.e., short swaps. These transpositions mimic microrearrangements of gene order in viruses and bacteria. We prove a (1/4)n 2 lower bound for sorting by adjacent swaps. We show upper bounds of (5/32)n 2 + O(n log n) and (7/8)n + O(log n) for sequential and parallel sorting, respectively, by short swaps.
X. Feng, Dr. Bhadrachalam Chitturi, and Sudborough, H., “Sorting Circular Permutations by Bounded Transpositions”, in Advances in Computational Biology, H. R. Arabnia New York, NY: Springer New York, 2010, pp. 725–736.