We consider the problem of sorting N-element inputs differing from already sorted sequences by t small changes. To perform this task we construct a constant depth comparator network that is applied periodically. The two constructions for this problem made by previous authors required O(log n + t) iterations of the network. Our construction requires O(log n + (log log N){sup}2(log t){sup}3) iterations which makes it asymptotically faster for t ≥ log N.
展开▼
机译：我们考虑将N元素输入排序与已经排序的序列相差t个小变化的问题。为了执行此任务，我们构建了一个恒定深度的比较器网络，该网络会定期应用。先前作者针对此问题进行的两种构造需要网络的O（log n + t）迭代。我们的构造需要O（log n +（log log N）{sup} 2（log t）{sup} 3）迭代，这使得t≥log N的渐近速度更快。
展开▼
