Generation of Long Sorted Runs on a Unidirectional Array

A parallel algorithm is presented for generation of long sorted runs as the first phase of sorting a large file. It can generate runs of length about 2mp + 2 on a unidirectional linear array of p processors each with a heap of size m. Internal computations can be completely overlapped with I/O, and almost only disk read time is required. Experiments with the algorithm and its variations have been conducted. The results show that all the versions can generate longer runs than a previous algorithm run on a bidirectional linear array.