IEICE TRANSACTIONS on Information
Exhaustive Computation to Derive the Lower Bound for Sorting 13 Items
Summary :
We have made an exhaustive computation to establish that 33 comparisons never sort 13 items. The computation was carried out within 10 days by a workstation. Since merge insertion sort [Ford, et al. A tournament problem, Amer. Math. Monthly, vol. 66, (1959)] uses 34 comparisons for sorting 13 items, our result guarantees the optimality of the sorting procedure to sort 13 items as far as the number of comparisons is concerned. The problem has been open for nearly three decades since Mark Wells discovered that 30 comparisons are required to sort 12 items in 1965.
- Publication
- IEICE TRANSACTIONS on Information Vol.E77-D No.9 pp.1027-1031
- Publication Date
- 1994/09/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Algorithm and Computational Complexity
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Shusaku SAWATO, Takumi KASAI, Shigeki IWATA, "Exhaustive Computation to Derive the Lower Bound for Sorting 13 Items" in IEICE TRANSACTIONS on Information,
vol. E77-D, no. 9, pp. 1027-1031, September 1994, doi: .
Abstract: We have made an exhaustive computation to establish that 33 comparisons never sort 13 items. The computation was carried out within 10 days by a workstation. Since merge insertion sort [Ford, et al. A tournament problem, Amer. Math. Monthly, vol. 66, (1959)] uses 34 comparisons for sorting 13 items, our result guarantees the optimality of the sorting procedure to sort 13 items as far as the number of comparisons is concerned. The problem has been open for nearly three decades since Mark Wells discovered that 30 comparisons are required to sort 12 items in 1965.
URL: https://global.ieice.org/en_transactions/information/10.1587/e77-d_9_1027/_p
Copy
@ARTICLE{e77-d_9_1027,
author={Shusaku SAWATO, Takumi KASAI, Shigeki IWATA, },
journal={IEICE TRANSACTIONS on Information},
title={Exhaustive Computation to Derive the Lower Bound for Sorting 13 Items},
year={1994},
volume={E77-D},
number={9},
pages={1027-1031},
abstract={We have made an exhaustive computation to establish that 33 comparisons never sort 13 items. The computation was carried out within 10 days by a workstation. Since merge insertion sort [Ford, et al. A tournament problem, Amer. Math. Monthly, vol. 66, (1959)] uses 34 comparisons for sorting 13 items, our result guarantees the optimality of the sorting procedure to sort 13 items as far as the number of comparisons is concerned. The problem has been open for nearly three decades since Mark Wells discovered that 30 comparisons are required to sort 12 items in 1965.},
keywords={},
doi={},
ISSN={},
month={September},}
Copy
TY - JOUR
TI - Exhaustive Computation to Derive the Lower Bound for Sorting 13 Items
T2 - IEICE TRANSACTIONS on Information
SP - 1027
EP - 1031
AU - Shusaku SAWATO
AU - Takumi KASAI
AU - Shigeki IWATA
PY - 1994
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E77-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 1994
AB - We have made an exhaustive computation to establish that 33 comparisons never sort 13 items. The computation was carried out within 10 days by a workstation. Since merge insertion sort [Ford, et al. A tournament problem, Amer. Math. Monthly, vol. 66, (1959)] uses 34 comparisons for sorting 13 items, our result guarantees the optimality of the sorting procedure to sort 13 items as far as the number of comparisons is concerned. The problem has been open for nearly three decades since Mark Wells discovered that 30 comparisons are required to sort 12 items in 1965.
ER -
English
