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).