Correction networks
Marcin Kik, Mirosław Kutyłowski, Marek Piotrów · 2003
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 /spl 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/spl middot/log n, for a small constant c. We present such networks of depth 4 log n+O(log/sup 2/ k log log n) with a small constant hidden behind the big "Oh". In particular, for k=o(2/spl radic/(log n/log log n)) the networks are of depth 4 log n+o(log n).