Algorithm to swap subsequences of 2 permutations

Let's call a case a[i] > a[j], such that i < j, a misplacement. Note that if elements are unique, a change in the number of misplacements induced by a swap (a, b, c) -> (c, a, b) is even. So, a necessary condition for such a permutation to be possible is the difference in the number of misplacements (transposition distance) has to be even.

Example:

{1,2,3,4,5,6}: 0 misplacements, {6,5,4,3,2,1}: 15 misplacements. The difference of 15 is odd, thus such permutation is not possible.

{1,3,4,2}: 2 misplacements (3 before 2, 4 before 2) {4,3,2,1}: 6 misplacements. The difference of 4 misplacements is even.

What is missing: I'm a bit lazy to formally prove this is a sufficient condition, i.e. that all even changes are possible. Also, this doesn't hold for sets with non-unique element - I'd guess any permutations are possible on those.

To calculate the number of misplacements, check Kendall tau distance algorithm. It'll need some adaptation, but will compute the distance in ~O(n log n).