For which $k$ I could sort permutation?

Question

Suppose we have some permutation:

$$p = a_{1}..a_{n}$$

We could inverse some subarray length of $k$. So my question is: for which $k$ I could sort my permutation using only my $k$-inverse? Obviously I could sort it with transposition (inverse of $a_{i}a_{i+1}$). But what about other $k$?

Answer 1

Let $P(k,n)$ be true iff sequences of length $n$ can be sorted by using only $k$-reverses. (All variables are natural numbers.)

Here are some partial results...

If $P(k,n)$, then $P(k,m)$ for any $m \ge n$.

Proof: Obvious by a method similar to bubble sort.

$\neg P(k,k)$ if $k \ge 3$.

Proof: Obvious.

$\neg P(k,k+1)$ if $k \ge 3$.

Proof: Adjacent items remain adjacent (with wrap-around).

$\neg P(2k+1,n)$.

Proof: Items at odd positions remain at odd positions.

$\neg P(4k,n)$.

Proof: Each $k$-reverse involves an even number of swaps, and hence a single swap is impossible.