Sorting networks: To the end and back again

作者：

Highlights：

• Faster sorting networks for 17, 19, and 20 inputs.

• 10 parallel steps are optimal for oblivious sorting of 17 inputs.

• Theoretical properties of the structure of sorting networks.

• Optimized SAT encoding for finding (depth-optimal) sorting networks.

摘要

•Faster sorting networks for 17, 19, and 20 inputs.•10 parallel steps are optimal for oblivious sorting of 17 inputs.•Theoretical properties of the structure of sorting networks.•Optimized SAT encoding for finding (depth-optimal) sorting networks.

论文关键词：Sorting networks,SAT-solving

论文评审过程：Received 26 June 2015, Revised 18 February 2016, Accepted 17 April 2016, Available online 28 April 2016, Version of Record 6 June 2019.

论文官网地址：https://doi.org/10.1016/j.jcss.2016.04.004