Some Remarks on p -Way Merging
Janet Fabri · SIAM Journal on Computing · 1977
A p-way merge of m items is usually implemented with sentinel keys of $\infty$ appended to the end of each input list, resulting in $m(p - 1)$ total comparisons. In this note, we analyze the number of comparisons performed when sentinel keys are not used. It is shown that the improvement in this case is very small.