Periodic constant depth sorting networks

         Marcin Kik, Miroslaw Kutylowski, Grzegorz Stachowiak


Comparator networks of constant depth can be used  for  sorting  in  the
following  way.  The  computation consists of a number of rounds, say t,
each round being a single run through the comparator network. The output
of  a  round j ( j<t) is used as the input for the round j+1. The output
of the round t is the output of the computation. In such a way,  we  may
apply  a  small comparator network for sorting long input sequences. The
main problem, however, is achieving a good computation time.

Odd-Even Transposition Sort gives a periodic sorting network of depth 2,
that  sorts n numbers in n/2 iterations. The network of depth 8 proposed
by Schwiegelshohn sorts n numbers in O(sqrt{n}log n) iterations. Krammer
modified  the  algorithm  and  obtained  a network of depth 6 sorting in
O(sqrt{nlog n}) iterations.

For a fixed but arbitrary  natural  number  k,  we  present  a  periodic
sorting  network  of depth O(k) that sorts n input numbers in O(n^{1/k})
steps.