Abstract:
The paper is concerned with a method for sorting by merger in a computer with one flow of commands and many flows of data, the computer consisting of $k$ parallel processors. The number which represents acceleration obtained in sorting by this method of an array of $N$ elements $N\gg k$ in comparison with the fastest possible sorting on a sequential computer approaches $\log_2N$ with $k$ fairly large.