I am interested in restricted sorting problem:
If we restrict sorting algorithms to use transpositions (swapping integers in two non-adjacent positions) and restrict the number of transpositions then some sequences are sortable and others are not.
Note that sequence $A$ may contain some repeated integers
Formally, the problem is:
Input: a sequence $A=[a_1, a_2, ..., a_{2N}]$ of $2N$ positive (possibly repeated) integers.
Question: Is it possible to sort sequence $A$ using $N$ transpositions of non-adjacent positions?
Is there a polynomial-time algorithm to solve this problem? Or Is it NP-complete?
This was posted on CS Theory long time ago without getting an answer.