Sorting on a ring of processors

We study the time necessary to sort on a ring of processors. We show that the amount of space available to each processor determines the time required. We prove a lower bound of 2n/2] − 1 steps for sorting on a ring of n processors, under the constraint that each processor retains only a single value at any time. In contrast, we show an algorithm that sorts in n/2] + 1 steps if each processor is allowed to store six values.