Proving that an arrangement of positive integers from $0$ to $m$ can be sorted in $m+1$ steps or fewer

Question

I have a list $L$ such that $L = a_0, a_1, ..., a_{m-1}, a_m$ such that L is an arrangement of the positive integers from $0$ to $m$. Let $$a' = L[a]$$ (as in, $a'$ is the element of $L$ in position $a$, starting from $0$); in general, let $$a^{(n)} = L[a^{(n-1)}]$$ with $a^{(1)} = a'$, $a^{(2)} = a'' = L[a']$, etc. and let $L^{(n)} = (a_0)^{(n)}, (a_1)^{(n)}, ..., (a_{m-1})^{(n)}, (a_m)^{(n)}$.

I would like to prove that for any $L$ that is an arrangement of positive integers $0$ to $m$:

1. There exists an $L^{(n)}$ such that all elements of $L$ satisfy $L[k] = k$, that is, $L$ is sorted from least to greatest.
2. The smallest $n$ such that $L^{(n)}$ is sorted from least to greatest satisfies the inequality $$0 ≤ n ≤ m+1$$

In other words, I am trying to prove that, if $L^{(n)}$ is sorted but $L^{(n-1)}$ is not, n will never be greater than the amount of elements in L. Any feedback on how to start would be greatly appreciated.

An example of this sorting process would be as follows, with $m = 5$ in this case: $$L = 5, 3, 0, 1, 2, 4$$ $$L' = L[5], L[3], L[0], L[1], L[2], L[4] = 4, 1, 5, 3, 0, 2$$ $$L'' = L[4], L[1], L[5], L[3], L[0], L[2] = 2, 3, 4, 1, 5, 0$$ $$L''' = L[2], L[3], L[4], L[1], L[5], L[0] = 0, 1, 2, 3, 4, 5$$ In this case, $n = 3$ and $m+1 = 6$, so $0 ≤ n ≤ m+1$.

Answer 1

Hagen von Eitzen’s comment says it all, rather compactly.

Your procedure amounts to treating $L$ as a permutation, which you then apply repeatedly until you get $[0,1,2,3,…]$, which corresponds, in your procedure, to the identity permutation - that permutation which, if you apply it to a list of numbers, doesn’t change it.

In the language of permutations, you are considering the group $S_{m+1}$ of permutations on $m+1$ elements. The “order” of a permutation is the number of times you have to repeat it to get to the identity - in your language, to sort the numbers.

HvE’s example for $m=6$ is $[1,2,0,4,5,6,3]$. This violates your hypothesis. The first part, $[1,2,0]$, sorts itself every 3 steps. The second part, $[4,5,6,3]$, sorts itself every 4 steps. So they will both be sorted only after 12 steps.

Answer 2

Maybe I'm confused, but I don't think it works. Suppose $$ L = [ 2, 0, 1]$$ Then I get $$ L' = [1, 2, 0]$$ and $$ L'' = [2, 0, 1]$$ and future iterations will just keep alternating $[2,0,1]$ and $[1,2,0]$, never reaching $[0,1,2]$.