We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
On the Average Case of MergeInsertion.
- Authors
Stober, Florian; Weiß, Armin
- Abstract
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.4005 n + 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.
- Subjects
ALGORITHMS
- Publication
Theory of Computing Systems, 2020, Vol 64, Issue 7, p1197
- ISSN
1432-4350
- Publication type
Article
- DOI
10.1007/s00224-020-09987-4