Fast and feasible periodic sorting networks of constant depth,
                Miroslaw Kutylowski, Krzysztof Lorys, 
                Brigitte Oesterdiekhoff, Rolf Wanka

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-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 T(n)) items  in
time  O(T(n)log n) and has layout area O(A 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 din IN. Then
we can construct a network of depth 3  based  on  a  d-dimensional  mesh
sorting n items in time O(n^(1/d) log^(O(d) n)).