Short Communication: Asynchronous parallel merging

An asynchronous scheduling strategy for use in conjunction with any sequential merging algorithm to implement an asynchronous parallel merging algorithm on an MIMD multiprocessor is presented. In particular, an asynchronous parallel implementation of the 2-way merge algorithm is described and used as a component in three versions of a parallel sorting algorithm. Their performance is compared when executed on the Sequent Balance 8000 multiprocessor.