SPEEDING UP SORTING ON AN ARRAY PROCESSOR.

Most algorithms on mesh-connected computers assume that the input elements are distributed one per processor. This has resulted in algorithms that require O(n**1 **/ **2 ) time to sort n elements on a standard mesh-connected computer that uses only local communication. Such an assumption also does not improve sorting on augmented mesh-connected computers, in which the standard mesh-connected computer is augmented either with a single broadcast bus or with row and column buses. By allowing more input elements to be stored in a processor it is shown that sorting can be speeded up to O(n**1 **/ **3 ) on such a computer. The same strategy also speeds up semigroup operations on a standard mesh-connected computer and its variants.