Proof of correctness odd-even sort

[HaritzPuerto]

Hello,

I have a question about the proof of correctness of the odd-even sort algorithm.

We have that COi <= max (AOk, BOi-k), where does it expression came from? k comes from the second lemma (there is k st. AEk <= CEi <= AEk+1 and BEi-k <= CEi <= BEi-k+1) but how can we link COi with AO and BO using the k index from the second lemma?

Thank you

[jeehoonkang]

• CO is the merge of AO and BO.
• Now suppose AO(k) >= BO(i-k). Then there exist at least i elements in CO that is <= AO(k). That i elements are: AO(1), AO(2), ..., AO(k), and BO(1), BO(2), ..., BO(i-k). So we have CO(i) <= AO(k).
• Suppose otherwise, BO(i-k) >= AO(k). Then by the same argument, we have CO(i) <= BO(i-k).
• Thus CO(i) <= max(AO(k), BO(i-k)).

[HaritzPuerto]

thank you