We consider the problem of sorting N-element inputs differing from already sorted sequences on t entries. To perform this task we construct a 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)~2(log t)~3) iterations which makes it faster for t log N.
展开▼
机译：我们考虑了对N元素输入进行排序的问题，该问题与已经对t条目进行排序的序列不同。为了执行此任务，我们构建了一个定期应用的比较器网络。先前作者针对此问题进行的两种构造需要网络的O（log n + t）迭代。我们的构造需要O（log n +（log log N）〜2（log t）〜3）迭代，这使得t >> log N更快。
展开▼
