The asymptotic complexity of merging networks
The asymptotic complexity of merging networks
Let M(m,n) be the minimum number of comparators needed in a comparator network that merges m elements x 1 ≤ x 2 ≤ … ≤ x m and n elements y 1 ≤ y 2 ≤ … ≤ y m , where n ≥ m. Batcher's odd-even merge yields the …