Parallel Sorting with Serial Memories

This correspondence examines the problem of sorting on a network of processors, where each processor consists of a single storage register and a small control unit capable of comparing two numbers and has a single serial memory attached to it. We show how to sort optimally on one- or two-dimensional arrays of p processors in time ¿(n + (n²/p²)) and ¿((n/¿p) + (n²/p²)), respectively. Because of the implementational advantages of serial memories, we feel that our architecture will be attractive for several applications.