Perfectly overlapped generation of long runs on a transputer array for sorting

Parallel algorithms are presented for generation of long sorted runs as the first phase of sorting a large file. They can generate runs of length about 2mp on a one-way linear array of p processors each with a heap of size m. Internal computations can be completely overlapped with I/O, and most of the output time can be overlapped with the input time; thus, almost only input time is required. Experiments with the algorithms and their variations have been conducted using transputers. Although the data transfer between transputers is restricted to only a single direction, the experimental results show that all the versions can generate longer runs than a previous algorithm for a two-way transputer array. © 1997 Elsevier Science B.V. © 1997 Elsevier Science B.V.