TY - JOUR
T1 - Sorting networks: To the end and back again
AU - Codish, Michael
AU - Cruz-Filipe, Luis
AU - Ehlers, Thorsten
AU - Müller, Mike
AU - Schneider-Kamp, Peter
PY - 2019/9
Y1 - 2019/9
N2 - New properties of the front and back ends of sorting networks are studied, illustrating their utility when searching for bounds on optimal networks. Search focuses first on the "out-sides" of the network and then on the inner part. Previous works focused on properties of the front end to break symmetries in the search. The new, out-side-in, properties shed understanding on how sorting networks sort, and facilitate the computation of new bounds on optimality. We present new, faster, parallel sorting networks for 17-20 inputs. For 17 inputs, we show that no sorting network using less layers exists.
AB - New properties of the front and back ends of sorting networks are studied, illustrating their utility when searching for bounds on optimal networks. Search focuses first on the "out-sides" of the network and then on the inner part. Previous works focused on properties of the front end to break symmetries in the search. The new, out-side-in, properties shed understanding on how sorting networks sort, and facilitate the computation of new bounds on optimality. We present new, faster, parallel sorting networks for 17-20 inputs. For 17 inputs, we show that no sorting network using less layers exists.
KW - SAT-solving
KW - Sorting networks
U2 - 10.1016/j.jcss.2016.04.004
DO - 10.1016/j.jcss.2016.04.004
M3 - Journal article
SN - 0022-0000
VL - 104
SP - 184
EP - 201
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
ER -