The Information-Theoretic Bound is Good for Merging

Let $A = (a_1 > \cdots > a_m )$ and $B = (b_1 > \cdots > b_n )$ be given ordered lists: also let there be given some order relations between $a_i $’s and $b_j $’s. Suppose that an unknown total order exists on $A \cup B$ which is consistent with all these relations ($ = a$ linear extension of the partial order) and we wish to find out this total order by comparing pairs of elements $a_t :b_s $. If the partial order has N linear extensions, then the Information Theoretic Bound says that $\log _2 N$ steps will be required in the worst case from any such algorithm. In this paper we show that there exists an algorithm which will take no more than $C\log _2 N$ comparisons where $C = (\log _2 ((\sqrt 5 + 1)/ 2))^{ -1} $. The computation required to determine the pair $a_t :b_s $ to be compared has length polynomial in $(m + n)$. The constant C is best possible. Many related results are reviewed.