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?

  • $\begingroup$ "I found a observation" is not a sufficient argument. You must justify. $\endgroup$ Feb 10 at 9:30
  • $\begingroup$ "Also we augment index of larger number to $A[i]$": no idea what this means. $\endgroup$ Feb 10 at 9:31
  • $\begingroup$ 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. $\endgroup$ Feb 10 at 9:33
  • $\begingroup$ @Mohammad.Rostami Could you show how you algorithm works for example on array $[9,6,8,7]$? How does it output the sorted array? $\endgroup$
    – John L.
    Feb 10 at 16:14
  • $\begingroup$ At the first iteration we have $[6,7,9,8]$ and array with be sort. $\endgroup$ Feb 11 at 17:10


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.