k-way merging and k-ary sorts
William A. Greene · 2002
A divide-and-conquer algorithm is given for merging k sorted lists, namely, recursively merge the first (k/2) lists, do likewise for the last (k/2) lists, then merge the two results. The author gets a tight bound for the expense of the worst case behavior of this merge. He shows the algorithm is cheapest among all similar divide-and-conquer approaches to k-way merging. He computes the expense of the k-ary sort; sometimes its expense is identical to that of the binary sort.>