An optimal parallel algorithm for integer sorting

We assume a parallel RAM model which allows both concurrent writes and concurrent reads of global memory. Our algorithms are randomized: each processor is allowed an independent random number generator. However our stated resource bounds hold for worst case input with overwhelming likelihood as the ... View More