The search functionality is under construction.

Author Search Result

[Author] Shusaku SAWATO(1hit)

1-1hit
  • Exhaustive Computation to Derive the Lower Bound for Sorting 13 Items

    Shusaku SAWATO  Takumi KASAI  Shigeki IWATA  

     
    PAPER-Algorithm and Computational Complexity

      Vol:
    E77-D No:9
      Page(s):
    1027-1031

    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.