# $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\le a\le...\le$ and $a\le a\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,a), (a,a), (a,a), \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\le a \le ... \le a[n]$. Then let assume that algorithm didn't compare $a to a$. Then we don't know minimum so we don't know order. If we compare $a to a$ adversary will answer $a \le a$. Then we will get exaclty the same problem with elements $a$ and $a$. 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