# $2$-sorted array. How to sort it in minimal number of comparisons ?

It is given array $2$-sorted array $a[1..n]$. $2$-sorted denotes that $a[1]\le a[3]\le...\le$ and $a[2]\le a[4]\le ..\le$

Obviously we may split array into two sorted arrays and then merge two arrays - it requires $n-2$ comparisons. However I think about lower bound. I believe that $n-2$ is lower bound number of comparisons, but I can't see a way to prove it. Can you give me a clue ?

• In fact merge requires $n-1$ comparisons. Think about the case $n=2$, for example. – Yuval Filmus Nov 16 '15 at 16:27

Hint:Show that the algorithm must compare the following pairs: $$(a[1],a[2]), (a[2],a[3]), (a[3],a[4]), \ldots, (a[n-1],a[n]).$$
For each comparison $(a[i],a[i+1])$, assume that you haven't compares $a[i]$ to $a[i+1]$ but you have done all other comparisons. Show that you still don't know the correct sorted order of the array.
• Ok, Adversary may swap elements such that $a[1]\le a[2] \le ... \le a[n]$. Then let assume that algorithm didn't compare $a[1] to a[2]$. Then we don't know minimum so we don't know order. If we compare $a[2] to a[1]$ adversary will answer $a[1] \le a[2]$. Then we will get exaclty the same problem with elements $a[2]$ and $a[3]$. It is clear that adverasry may make algorithm do $n-1$ comparisons - there pairs that you hinted. What about this reasoning? – user40545 Nov 16 '15 at 20:16