Every sequence is sortable in the worst-case by a $O(n^2)$. However, if we restrict sorting primitive, we get an interesting problem. I am interested in this sorting problem:
Input: a sequence $A$ of $2N$ positive integers.
Question: Is it possible to sort sequence $A$ using only $N$ transpositions?
Each transposition swaps two non-adjacent elements $a_i$ and $a_j$ in $A$ (two elements are not adjacent if $|i−j|>1$). My intuition is that the problem should be $NP$-complete.
Is this problem $NP$-complete? Is it polynomial-time decidable?
One such sequence: A=$[7,5, 9, 10, 2, 8, 1, 6, 3, 4]$. Swap pairs (4,10), (7,1),(8,6), (3,9), and (2,5).
In general, numbers in the sorted sequence are not nesseraily consecutive.