Suppose A is a sorted list of length n and B is a sorted list of length 2. I am asked to find the minimum number of comparisons that any algorithm must do in order to merge these lists. I am also given an analysis of this which does not use a comparison tree, but argues combinatorially that the number of leaves must be $\binom{n+1}{2}$ and that the height $h$ must satisfy $2^h \geq \binom{n+1}{2}$.

However, I get a different answer when I actually draw the comparison tree. As I reason, the comparison tree has two branches at the top, one corresponding to a1 < b1 and one corresponding to a1 > b1. If you follow the right branch right again this corresponds to a1 > b1 and a1 > b2 and at this point the tree terminates in a leaf. No more comparisons are needed because the merge can simply make each comparison, but the bs in the merge list, and dump all the rest of the as in after.

That's not the interesting part but hopefully it is a simple consideration that makes clear how I'm approaching this. The left branch, in which you get a1 < b1 and a2 < b1 and ... and an < b1 corresponds to going left and left and ... and left. There are n comparisons on this branch. In fact I think you can get one more if instead of an < b1 at the end you go right and say an > b1 and then an < b2 (or an > b2 since at this point it doesn't matter, both sides are a leaf). So really the tree has height exactly n+1. Right? Or am I misunderstanding something?


Your Answer

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

Browse other questions tagged or ask your own question.