$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 ?
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.