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

| cite | improve this answer | |
  • $\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 '15 at 20:16
  • 1
    $\begingroup$ Something of this sort. $\endgroup$ – Yuval Filmus Nov 16 '15 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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