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 ?