<%@ page language="java" contentType="text/html" %> <%-- Include common initialisation code --%> <%@ include file="/arch/common.jsp" %> <%-- The current tab --%> <% String currentTab = "Research"; %> <%-- Content of navigation pane --%> <%@ include file="nav.jsp" %> <% showCurrentLink=true; %> <%-- Current navigation location --%> <% String currentNav = "Reports and Theses"; %> <%-- Include the code for the document header --%> <%@ include file="/arch/header.jsp" %>

Research Report CS-RR-216

<%-- Include the code for the lines and navigation --%> <%@ include file="/arch/middle.jsp" %>

Per Bro Miltersen, M.S. Paterson and Jun Tarui, The Asymptotic Complexity of Merging Networks (April 1, 1992).

Abstract

Let M(m, n) be the minimum number of comparators in a comparator network that merges two ordered chains x_1 2 x_2 2 . . . 2 x_m and y_1 2 y_2 . . . 2 y_n, where n 3 m. Batcher's odd-even merge yields the following upper bound: M(m, n) 2 (m + n)/2. log_2 (m + 1) + O (n), e.g., M (n, n) 2 n log_2 n + O(n). Floyd (for M(n, n)), and then Yao and Yao (for M(m, n)) have shown the following lower bounds: M(m, n) 3 n /2. log_2 (m + 1); M (n, n) 3 n /2. log_2 n + O (n). We prove a new lower bound that matches the upper bound asymptotically: M (m, n) 3 (m + n)/2. log_2 (m + 1) - O (m), e.g., M (n, n) 3 n log_2 n - O (n). Our proof technique extends to give similarly tight lower bounds for the size of monotone Boolean circuits for merging, and for the size of switching networks capable of realizing the set of permutations that arise from merging.

Download

cs-rr-216.ps.gz

<%-- Include the code for the document footer --%> <%@ include file="/arch/footer.jsp" %>