
arXiv: 1702.08443
This paper offers two elementary yet precise derivations of an exact formula \[ W(n) = \sum_{i=1} ^{n} \lceil \lg i \rceil = n \lceil \lg n \rceil - 2^{\lceil \lg n \rceil} + 1 \] for the maximum number $ W(n) $ of comparisons of keys performed by $ {\tt MergeSort} $ on an $ n $-element array. The first of the two, due to its structural regularity, is well worth carefully studying in its own right. Close smooth bounds on $ W(n) $ are derived. It seems interesting that $ W(n) $ is linear between the points $ n = 2^{\lfloor \lg n \rfloor} $ and it linearly interpolates its own lower bound $ n \lg n - n + 1 $ between these points.
25 pages, 12 figures, three of which contain working Java methods
FOS: Computer and information sciences, 68W40 Analysis of algorithms, Discrete Mathematics (cs.DM), G.2.0, G.2.1, G.2.2, Computational Complexity (cs.CC), F.2.2; G.2.0; G.2.1; G.2.2, Computer Science - Computational Complexity, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), F.2.2, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, 68W40 Analysis of algorithms, Discrete Mathematics (cs.DM), G.2.0, G.2.1, G.2.2, Computational Complexity (cs.CC), F.2.2; G.2.0; G.2.1; G.2.2, Computer Science - Computational Complexity, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), F.2.2, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
