{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:36Z","timestamp":1740109416965,"version":"3.37.3"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2020,6,30]],"date-time":"2020-06-30T00:00:00Z","timestamp":1593475200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,6,30]],"date-time":"2020-06-30T00:00:00Z","timestamp":1593475200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["DI 435\/7-1"],"award-info":[{"award-number":["DI 435\/7-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2020,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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 <jats:inline-formula><jats:alternatives><jats:tex-math>$n \\log n - 1.4005n + o(n)$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n<mml:mi>n<\/mml:mi>\n<mml:mi>log<\/mml:mi>\n<mml:mi>n<\/mml:mi>\n<mml:mo>\u2212<\/mml:mo>\n<mml:mn>1.4005<\/mml:mn>\n<mml:mi>n<\/mml:mi>\n<mml:mo>+<\/mml:mo>\n<mml:mi>o<\/mml:mi>\n<mml:mo>(<\/mml:mo>\n<mml:mi>n<\/mml:mi>\n<mml:mo>)<\/mml:mo>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula> 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 <jats:italic>n<\/jats:italic> 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\u2019s combination of merging and MergeInsertion as well as to the recent combined algorithm with (1,2)-Insertionsort by Iwama and Teruyama.<\/jats:p>","DOI":"10.1007\/s00224-020-09987-4","type":"journal-article","created":{"date-parts":[[2020,6,30]],"date-time":"2020-06-30T10:03:46Z","timestamp":1593511426000},"page":"1197-1224","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On the Average Case of MergeInsertion"],"prefix":"10.1007","volume":"64","author":[{"given":"Florian","family":"Stober","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7645-5867","authenticated-orcid":false,"given":"Armin","family":"Wei\u00df","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,6,30]]},"reference":[{"issue":"12","key":"9987_CR1","doi-asserted-by":"publisher","first-page":"1315","DOI":"10.1002\/spe.4380251203","volume":"25","author":"HJ Boehm","year":"1995","unstructured":"Boehm, H.J., Atkinson, R., Plass, M.: Ropes: an alternative to strings. Softw. Pract. Exper. 25(12), 1315\u20131330 (1995)","journal-title":"Softw. Pract. Exper."},{"issue":"1","key":"9987_CR2","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/BF01934989","volume":"25","author":"T Bui","year":"1985","unstructured":"Bui, T., Thanh, M.: Significant improvements to the Ford-Johnson algorithm for sorting. BIT Numer. Math. 25(1), 70\u201375 (1985)","journal-title":"BIT Numer. Math."},{"key":"9987_CR3","doi-asserted-by":"crossref","unstructured":"Edelkamp, S., Wei\u00df, A.: QuickXsort: Efficient Sorting with $n \\log n - 1.399n + o(n)$ Comparisons on Average. In: CSR 2014 Proc., pp 139\u2013152 (2014)","DOI":"10.1007\/978-3-319-06686-8_11"},{"issue":"3","key":"9987_CR4","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1007\/s00453-019-00634-0","volume":"82","author":"S Edelkamp","year":"2020","unstructured":"Edelkamp, S., Wei\u00df, A., Wild, S.: Quickxsort: A, fast sorting scheme in theory and practice. Algorithmica 82(3), 509\u2013588 (2020). https:\/\/doi.org\/10.1007\/s00453-019-00634-0","journal-title":"Algorithmica"},{"issue":"5","key":"9987_CR5","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1080\/00029890.1959.11989306","volume":"66","author":"LR Ford","year":"1959","unstructured":"Ford, L.R., Johnson, S.M.: A tournament problem. Am. Math. Mon. 66(5), 387\u2013389 (1959)","journal-title":"Am. Math. Mon."},{"issue":"1","key":"9987_CR6","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1137\/0201004","volume":"1","author":"FK Hwang","year":"1972","unstructured":"Hwang, F.K., Lin, S.: A simple algorithm for merging two disjoint linearly ordered sets. SIAM J. Comput. 1(1), 31\u201339 (1972)","journal-title":"SIAM J. Comput."},{"key":"9987_CR7","doi-asserted-by":"crossref","unstructured":"Iwama, K., Teruyama, J.: Improved Average Complexity for Comparison-Based Sorting. In: Workshop on Algorithms and Data Structures, pp 485\u2013496. Springer, New York (2017)","DOI":"10.1007\/978-3-319-62127-2_41"},{"key":"9987_CR8","volume-title":"The art of computer programming, volume 3: (2nd edn.) sorting and searching","author":"DE Knuth","year":"1998","unstructured":"Knuth, D.E.: The art of computer programming, volume 3: (2nd edn.) sorting and searching. Addison wesley longman, redwood city (1998)"},{"issue":"3","key":"9987_CR9","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1145\/322139.322145","volume":"26","author":"GK Manacher","year":"1979","unstructured":"Manacher, G.K.: The Ford-Johnson sorting algorithm is not optimal. J. ACM 26(3), 441\u2013456 (1979)","journal-title":"J. ACM"},{"issue":"2","key":"9987_CR10","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/s00453-004-1100-7","volume":"40","author":"M Peczarski","year":"2004","unstructured":"Peczarski, M.: New results in minimum-comparison sorting. Algorithmica 40(2), 133\u2013145 (2004)","journal-title":"Algorithmica"},{"issue":"3","key":"9987_CR11","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.ipl.2006.09.001","volume":"101","author":"M Peczarski","year":"2007","unstructured":"Peczarski, M.: The Ford-Johnson algorithm still unbeaten for less than 47 elements. Inf. Process. Lett. 101(3), 126\u2013128 (2007)","journal-title":"Inf. Process. Lett."},{"key":"9987_CR12","doi-asserted-by":"crossref","unstructured":"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 \u201992, Proc., pp 489\u2013498 (1992)","DOI":"10.1007\/3-540-56279-6_101"},{"key":"9987_CR13","unstructured":"Stober, F.: Source code and generated data https:\/\/github.com\/CodeCrafter47\/merge-insertion (2018)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-09987-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-020-09987-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-09987-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T23:24:01Z","timestamp":1625009041000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-020-09987-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,30]]},"references-count":13,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["9987"],"URL":"https:\/\/doi.org\/10.1007\/s00224-020-09987-4","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2020,6,30]]},"assertion":[{"value":"30 June 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}