Correction Networks

                  M. Kik, M. Kutylowski and M. Piotrow

We consider the problem of sorting  sequences  obtained  from  a  sorted
sequence  of  n  keys  by  changing the values of at most k keys at some
unknown positions. Since even for k=1 a lower bound Omega(log n) on  the
number  of  parallel  comparison  steps  applies, any comparator network
solving this problem  cannot  be  asymptotically  faster  than  the  AKS
sorting  network.  We  design  a  comparator  network  which  sorts  the
sequences considered for a large range of k's, has a simple architecture
and  achieves a runtime c log n, for a small constant c. We present such
networks of depth
                4 log n+O( log^2 k  log log n) 
with a small constant hidden behind the big ``Oh''. In particular, for
                k=o(2^(sqrt(log n/ log log n))) 
the networks are of depth 4 log n+o( log n).