May 1996, 32pp.
In this paper we study the problem of sorting n keys on the Bulk-Synchronous Parallel (BSP) model, which abstracts the characteristics of a parallel machine into three numerical parameters p, L, and g, corresponding to processors, periodicity, and bandwidth, respectively. We establish lower bounds for parallel time as a function of the available communication throughput of the system, and derive transportable algorithms that can be applied for a wide range of values of the parameters p, L, and g, whose performance matches the lower bounds. While the algorithms are fairly simple themselves, descriptions of their behaviour in terms of these parameters is somewhat involved. The main reward of quantifying these complications, is that it allows software to be written once and for all, ie, architecture independent software capable of delivering scalable performance for a wide class of applications on a variety of parallel systems.