The Takeoff Towards Optimal Sorting Networks

Abstract

A complete set of filters $F_n$ for the optimal-depth $n$-input sorting network problem is such that if there exists an $n$-input sorting network of depth $d$ then there exists one of the form $C \oplus C'$ for some $C \in F_n$. Previous work on the topic presents a method for finding complete set of filters $R_{n, 1}$ and $R_{n, 2}$ that consists only of networks of depths one and two respectively, whose outputs are minimal and representative up to permutation and reflection. Our main contribution is a practical approach for finding a complete set of filters $R_{n, 3}$ containing only networks of depth three whose outputs are minimal and representative up to permutation and reflection. In previous work, we have developed a highly efficient algorithm for finding extremal sets ( i.e. outputs of comparator networks; itemsets; ) up to permutation. In this paper we present a modification to this algorithm that identifies the representative itemsets up to permutation and reflection. Hence, the presented practical approach is the successful combination of known theory and practice that we apply to the domain of sorting networks. For $n < 17$, we empirically compute the complete set of filters $R_{n, 2}$, $R_{n, 3}$, $R_{n, 2} \upharpoonright w $ and $R_{n, 3}^w$ of the representative minimal up to permutation and reflection $n$-input networks, where all but $R_{n, 2}$ are novel to this work.