%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 }