# Proving correctness of a particular algorithm

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?

• "I found a observation" is not a sufficient argument. You must justify. Feb 10 at 9:30
• "Also we augment index of larger number to $A[i]$": no idea what this means. Feb 10 at 9:31
• The global argument does not seem correct. When you apply the algorithm to $n=k+1$, we don't know where the additional element goes, and that can break the sort of the $k$ first elements and induction is not granted. Feb 10 at 9:33
• @Mohammad.Rostami Could you show how you algorithm works for example on array $[9,6,8,7]$? How does it output the sorted array? Feb 10 at 16:14
• At the first iteration we have $[6,7,9,8]$ and array with be sort. Feb 11 at 17:10