We analyzed Van Voorhis 16-key network because it is faster than the merge-sorting networks for 16 keys (9 steps instead of 10 steps). To help better understand the behavior of this network, we used the relabeling technique. We re-labeled the network by exchanging K3 with K8 and by exchanging K7 with K12. This, resulted in a more logical placement of the 14 keys in the three sets between K0 and K15 since it put: K11 through K14 in the top set; K5 through K10 in the middle set; and K1 through K4 in the bottom set. When we drew the Knuth diagram for the re-labeled network , we found that: the first six steps partition the keys into four 4-key groups with every key in each group less than or equal to every key in the next higher group; steps 5 through 8 sort the keys within each group; and step 9 finishes sorting all the remaining cases to complete the sort of all 16 keys. Thus, relabeling this network helped us realize that it uses the well-known divide-and-conquer strategy to sort the 16 input leys.
%0 Book Section
%1 haddar11_5
%A Al-Haj Baddar, Sherenaz W.
%A Batcher, Kenneth E.
%B Designing Sorting Networks
%D 2011
%I Springer New York
%K algorithm baddar.batcher sorting sorting.network textbook
%P 27-33
%R 10.1007/978-1-4614-1851-1_5
%T A 16-Key Sorting Network
%X We analyzed Van Voorhis 16-key network because it is faster than the merge-sorting networks for 16 keys (9 steps instead of 10 steps). To help better understand the behavior of this network, we used the relabeling technique. We re-labeled the network by exchanging K3 with K8 and by exchanging K7 with K12. This, resulted in a more logical placement of the 14 keys in the three sets between K0 and K15 since it put: K11 through K14 in the top set; K5 through K10 in the middle set; and K1 through K4 in the bottom set. When we drew the Knuth diagram for the re-labeled network , we found that: the first six steps partition the keys into four 4-key groups with every key in each group less than or equal to every key in the next higher group; steps 5 through 8 sort the keys within each group; and step 9 finishes sorting all the remaining cases to complete the sort of all 16 keys. Thus, relabeling this network helped us realize that it uses the well-known divide-and-conquer strategy to sort the 16 input leys.
%& 5
%@ 978-1-4614-1850-4
@inbook{haddar11_5,
abstract = {We analyzed Van Voorhis 16-key network because it is faster than the merge-sorting networks for 16 keys (9 steps instead of 10 steps). To help better understand the behavior of this network, we used the relabeling technique. We re-labeled the network by exchanging K[3] with K[8] and by exchanging K[7] with K[12]. This, resulted in a more logical placement of the 14 keys in the three sets between K[0] and K[15] since it put: K[11] through K[14] in the top set; K[5] through K[10] in the middle set; and K[1] through K[4] in the bottom set. When we drew the Knuth diagram for the re-labeled network , we found that: the first six steps partition the keys into four 4-key groups with every key in each group less than or equal to every key in the next higher group; steps 5 through 8 sort the keys within each group; and step 9 finishes sorting all the remaining cases to complete the sort of all 16 keys. Thus, relabeling this network helped us realize that it uses the well-known divide-and-conquer strategy to sort the 16 input leys.},
added-at = {2014-04-20T00:48:29.000+0200},
author = {Al-Haj Baddar, Sherenaz W. and Batcher, Kenneth E.},
biburl = {https://www.bibsonomy.org/bibtex/266ccebbd76eff04d1c9b635e86a5a3c6/ytyoun},
booktitle = {Designing Sorting Networks},
chapter = 5,
doi = {10.1007/978-1-4614-1851-1_5},
interhash = {457c5633da9d8d12d3465c30060ad22d},
intrahash = {66ccebbd76eff04d1c9b635e86a5a3c6},
isbn = {978-1-4614-1850-4},
keywords = {algorithm baddar.batcher sorting sorting.network textbook},
language = {English},
pages = {27-33},
publisher = {Springer New York},
timestamp = {2016-10-27T12:46:24.000+0200},
title = {A 16-Key Sorting Network},
year = 2011
}