Fast and Feasible Periodic Sorting Networks of Constant Depth

A periodic comparator network has depth (or period) k, if for every t ? k, the compare-exchange operations performed at step t are executed between exactly the same registers as at step t \Gamma k. We introduce a general method that converts an arbitrary comparator network that sorts n items in time T (n) and that has layout area A into a periodic sorting network of depth 5 that sorts \Theta(n \Delta T (n)) items in time O(T (n) \Delta log n) and has layout area O(A \Delta T (n)). This scheme applied to the AKS network yields a depth 5 periodic comparator network that sorts in time O(log 2 n). More practical networks with runtime O(log 3 n) can be obtained from Batcher's networks. Developing the techniques for the main result, we improve some previous results: Let us fix a d 2 N. Then we can construct a network of depth 3 based on a d-dimensional mesh sorting n items in time O(n 1=d \Delta log O(d) n)