Periodic merging networks  
Miroslaw Kutylowski, Krzysztof Lorys, Brigitte Oesterdiekhoff

We  consider  the  problem  of  merging two sorted sequences on constant
degree networks using comparators only. The classical  solution  to  the
problem  are  the networks based on Batcher's Odd-Even Merge and Bitonic
Merge running in log(2n) time. Due to the obvious log n lower bound  for
the runtime, this is time-optimal.

We present new merging networks that have  a  novel  property  of  being
periodic:  for  some  (small)  constant  k,  each processing unit of the
network performs the same operations at steps t and t+k (as long as  t+k
does   not  exceed  the  runtime.)  The  only  operations  executed  are
compare-exchange operations, just like in  the  case  of  the  Batcher's
networks.  The  architecture  of the networks is very simple, easy to be
laid out. The runtimes achieved are c log n, for a small constant c.