WORK-TIME OPTIMAL K-MERGE ALGORITHMS ON THE PRAM

For 2 less than or equal to k less than or equal to n, the k-merge pro blem is to merge a collection of k sorted sequences of total length n into a new sorted sequence. The k-merge problem is fundamental as it p rovides a common generalization of both merging and sorting. The main contribution of this work is to give simple and intuitive work-time op timal algorithms for the k-merge problem on three PRAM models, thus se ttling the status of the k-merge problem. We first prove that Omega(n log k) work is required to solve the k-merge problem on the PRAM model s. We then show that the EREW-PRAM and both the CREW-PRAM and the CRCW require Omega(log n) time and Omega(log log n + log k) time, respecti vely, provided that the amount of work is bounded by O(n log k). Our f irst k-merge algorithm runs in Theta(log n) time and performs Theta(n log k) work on the EREW-PRAM. Finally, we design a work-time optimal C REW-PRAM k-merge algorithm that runs in Theta(log log n + log k) time and performs Theta(n log k) work. This latter algorithm is also work-t ime optimal on the CRCW-PRAM model. Our algorithms completely settle t he status of the k-merge problem on the three main PRAM models.