On the Average Case of MergeInsertion
Tóm tắt
MergeInsertion, also known as the Ford-Johnson algorithm, is a sorting algorithm which, up to today, for many input sizes achieves the best known upper bound on the number of comparisons. Indeed, it gets extremely close to the information-theoretic lower bound. While the worst-case behavior is well understood, only little is known about the average case. This work takes a closer look at the average case behavior. In particular, we establish an upper bound of
$n \log n - 1.4005n + o(n)$
comparisons. We also give an exact description of the probability distribution of the length of the chain a given element is inserted into and use it to approximate the average number of comparisons numerically. Moreover, we compute the exact average number of comparisons for n up to 148. Furthermore, we experimentally explore the impact of different decision trees for binary insertion. To conclude, we conduct experiments showing that a slightly different insertion order leads to a better average case and we compare the algorithm to Manacher’s combination of merging and MergeInsertion as well as to the recent combined algorithm with (1,2)-Insertionsort by Iwama and Teruyama.
Tài liệu tham khảo
Boehm, H.J., Atkinson, R., Plass, M.: Ropes: an alternative to strings. Softw. Pract. Exper. 25(12), 1315–1330 (1995)
Bui, T., Thanh, M.: Significant improvements to the Ford-Johnson algorithm for sorting. BIT Numer. Math. 25(1), 70–75 (1985)
Edelkamp, S., Weiß, A.: QuickXsort: Efficient Sorting with \(n \log n - 1.399n + o(n)\) Comparisons on Average. In: CSR 2014 Proc., pp 139–152 (2014)
Edelkamp, S., Weiß, A., Wild, S.: Quickxsort: A, fast sorting scheme in theory and practice. Algorithmica 82(3), 509–588 (2020). https://doi.org/10.1007/s00453-019-00634-0
Ford, L.R., Johnson, S.M.: A tournament problem. Am. Math. Mon. 66(5), 387–389 (1959)
Hwang, F.K., Lin, S.: A simple algorithm for merging two disjoint linearly ordered sets. SIAM J. Comput. 1(1), 31–39 (1972)
Iwama, K., Teruyama, J.: Improved Average Complexity for Comparison-Based Sorting. In: Workshop on Algorithms and Data Structures, pp 485–496. Springer, New York (2017)
Knuth, D.E.: The art of computer programming, volume 3: (2nd edn.) sorting and searching. Addison wesley longman, redwood city (1998)
Manacher, G.K.: The Ford-Johnson sorting algorithm is not optimal. J. ACM 26(3), 441–456 (1979)
Peczarski, M.: New results in minimum-comparison sorting. Algorithmica 40(2), 133–145 (2004)
Peczarski, M.: The Ford-Johnson algorithm still unbeaten for less than 47 elements. Inf. Process. Lett. 101(3), 126–128 (2007)
Reinhardt, K.: Sorting In-Place with a Worst Case Complexity of N Log N-1.3N + O(logn) Comparisons and Epsilon N Log N + O(1) Transports. In: Algorithms and Computation, ISAAC ’92, Proc., pp 489–498 (1992)
Stober, F.: Source code and generated data https://github.com/CodeCrafter47/merge-insertion (2018)