Heap Sort, Quick Sort, Counting Sort, Radix Sort, Bucket Sort are some of the sorting algorithms that you might be aware of, however they are designed for serial computers. Random-access machine model puts a hard limit on the speed of these algorithms since only one operation can be executed at a time. Enter Sorting Networks — parallel circuits comprised of wires and comparators that sort values in a sub-linear runtime. Since Sorting Networks are deterministic, data-oblivious, fixed, and can easily be implemented on hardware, they are really appealing. Especially since on top of merging and sorting, we can use them to make Switching Networks, Multi-Access Memory.

![sorting_network][sorting_network]

We explore construction of such Sorting Networks via NEAT (Neuroevolution of Augmenting Topologies). We start off with generation of random networks, they breed, create crossover children, mutate, and the least-fit children networks are dropped, allowing for only the ‘fitter’ generations to breed. We introduce a new NEAT mutation for our use case: mutate_transfer, wherein we mutate the transfer function of each node to either min(x) or max(x). This would give you a sense how we loosely use NEAT algorithm for generation of Sorting Networks. Since, most networks will generate incorrect permutations in the beginning, instead of using zero-one principle to check the correctness of each network, we measure the fitness of networks by L-1 norms of permutation matrices. This takes into account similar ordered subsequences. After multiple generations, we explore the properties of final sorting network.

Traditionally, a sorting network comprises of modules, namely Half-Cleaners and Bitonic Sorters. We explore how we can potentially generalize this composition using NEAT. Finally, we compare our method to AKS, Batcher odd-even mergesort, and how genetic algorithms been previously used to tackle this problem.

[sorting_network] : https://upload.wikimedia.org/wikipedia/commons/thumb/9/9b/SimpleSortingNetworkFullOperation.svg/1300px-SimpleSortingNetworkFullOperation.svg.png