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 ?

  • $\begingroup$ In fact merge requires $n-1$ comparisons. Think about the case $n=2$, for example. $\endgroup$ Nov 16, 2015 at 16:27

1 Answer 1


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.

  • $\begingroup$ 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? $\endgroup$
    – user40545
    Nov 16, 2015 at 20:16
  • 1
    $\begingroup$ Something of this sort. $\endgroup$ Nov 16, 2015 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.