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]. (C) 2019 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (https://creativecommons.org/licenses/by-nc-nd/4.0/) Peer-review under responsibility of KES International.