Suppose there is an array $A[1..n]$.$A$ contains a permutation of $\{1,2,3,\dots,n\}$.
We run the following algorithm $m$ times to sort $A$:
for each odd index of $A$ from left to right ,respectively, put $A[i]$ be the minimum of its and right adjacent (if exists). Also we store index of larger number for $A[i]$.
for each even index of $A$ from left to right ,respectively, put $A[i]$ be the minimum of it and right adjacent (if exists).Also we store index of larger number for $A[i]$.
I guess after $ \lceil \frac{n}{2}\rceil $ the algorithm sort number in increasing order. To prove my guess I try to use induction as follow:
For $n=1$ obviously the algorithm works correctly. Suppose it work for $n=k$ now to extend this assumption to $n=k+1$ I found a observation that after at most $ \lceil \frac{k+1}{2}\rceil $ largest and smallest elements will be in their correct place, now how I can conclude that all elements also be in their correct place after $ \lceil \frac{n}{2}\rceil $ repeating of the algorithm?
