More size-optimal algorithms
Morwenn opened this issue · 3 comments
More size-optimal sorting networks have been discovered recently thanks to several research projects (well, not size-optimal per se, but as optimal as we could find). The paper Using Symmetry and Evolutionary Search to Minimize Sorting Networks by Valsalam and Miikkulainen provides sorting networks using less compare-exchange units for sizes 17, 18, 19, 20, 21, 22 and 23 (even though the one of size 23 isn't better than sorting both halves of the array with the sorting networks of sizes 12 and 11 then using a Batcher's merge network to merge the two sorted halves).
I think that the "Best" algorithm could be extended to provide the best known size-optimal networks until size 32.
You can find them directly by looking up the names in your favourite search engine. Not sure whether it's legal or not, so I don't want to directly share the links, just in case :p
Valsalam and Miikkulainen's paper is available on the University of Texas's web site, while Codish, Cruz-Filipe, et al "are on ResearchGate and have made the full-text available on their profiles" according to the ResearchGate site, so I think we're safe in linking to the papers, and I'll do so:
"Using Symmetry and Evolutionary Search to Minimized Sorting Networks"
http://nn.cs.utexas.edu/downloads/papers/valsalam.jmlr13.pdf
"Sorting Networks: to the End and Back Again",
https://www.researchgate.net/publication/279864367_Sorting_Networks_to_the_End_and_Back_Again
for anyone else looking here. Thank you for the titles. I'll read them and figure out how to include them.