Minimum Number of Comparators in (6, 6)-Merging Network

摘要

The minimum number of comparators in a (6,6)-merging network is shown to be 17. The number has been known to be either 16 or 17 [See Knuth, The Art of Computer Programming Vol.3: Sorting and Searching, p.230]. Minimum numbers for (n,n)-merging netwerks, 1 ≤ n ≤ 9, n ≠ 6, were already known. The problem had been open for more than two decades.