Greedy Best-First Search for the Optimal-Size Sorting Network Problem

In this paper we present an effective algorithm for creating minimal-size sorting networks. Our approach is based on incrementally constructing sets of sorting networks, starting from a specified prefix and adding gradually new comparators. At each step, in order to limit the size of these sets, only the most promising candidates are considered. We introduce a novel rule for implementing the selection of candidates, based on analyzing the structure of a network’s output, instead of simply considering its size. For 16 wires, the running time necessary to determine a sorting network was reduced up to 90 times, compared to state-of-the-art results [21].