I'm studying the odd-even algorithm. I've read this lecture note and I don't understand one point in his proof of correctness.
Thus it remains to prove that for all $i$, $E[i] \le D[i+1]$, or in other words, $\textrm{max}(C_o[i+1],C_e[i]) \le \textrm{min}(C_o[i+2],C_e[i+1])$. Equivalently, we need to prove that for all $i$, we have $(i)$ $C_o[i+1] \le C_o[i+2]$, \emph$(ii)$ $C_o[i+1] \le C_e[i+1]$, $(iii)$ $C_e[i] \le C_o[i+2]$, and $(iv)$ $C_e[i] \le C_e[i+1]$. Out of the four, $(i)$, $(ii)$, and $(iv)$ are trivial to prove. Now let's prove $(iii)$.
But I don't think $(ii)$ is trivial. Can you help me to prove that? Thanks
P/S: I have to note that, in the base case, where only 2 values go into merge func. merge func ~ is equivalent to compare function. (i.e: compare ((a),(b)) = (a>b) ? (a,b) : (b,a))
Let $A_o[k]$ and $B_o[l]$ be the greatest values of $A_o$ and $B_o$ such that $A_o[k]\leq C_o[i+1]$ and $B_o[l]\leq C_o[i+1]$ . We have $k+l=i+1$. Moreover, we can suppose WLOG that $A_o[k]=C_o[i+1]$.
We immediately see that $A_e[j] \leq C_o[i+1]$ for $j< k$ and $B_e[j] \leq C_o[i+1]$ for $j<l$. The only other $C_e$ value that can eventually be lower than $C_o[i+1]$ is $B_e[l]$, all the other $C_e$ values must be greater.
We count at most $(k-1)+(l-1) +1 = i$ values of $C_e$ that can be lower than $C_o[i+1]$, but $C_e[i+1]$ will necessarily be greater.