Efficient Filters for the Simulated Evolution of Small Sorting Networks

A sorting network is a mathematical model of an oblivious sorting algorithm-that is, a sorting algorithm in which all comparisons take place in a fixed order at predetermined positions in the list. The search for sorting networks of optimal size is an old problem. Asymptotically optimal networks of size O(n log n) are known, where n is the number of inputs, but the hidden constants are enormous. Genetic algorithms have been used to tackle this problem in a number of studies since the early 1990s, often focusing on the historically interesting case of 16 inputs. In this special case, the best known bound of 60 comparisons has been attained, but often through the use of a particular, highly structured, initial sequence of comparisons that narrows the search space by filtering out all but a small core of input sequences. We make explicit the concept of a filter-a fixed sequence of comparisons to be extended to a sorting network through a stochastic process-and present a new construction for any perfect square number of inputs. In the case of 9 inputs, we extend the filter to a sorting network of size 25, attaining the best known bound. For 16 and 25 inputs, we present a simple GA variant that extends the filter to produce small sorting networks with highly regular structure.