Elementary yet Precise Best-Case Analysis of MergeSort with an Application to the Sum of Digits Problem

An exact formula B(n)=n2(⌊lgn⌋+1)−∑k=0⌊lgn⌋2kZigzag(n2k+1), where Zigzag(x)=min(x−⌊x⌋,⌈x⌉−x), for the minimum number B(n) of comparisons of keys performed by MergeSort on an n-element array is derived and analyzed. The said formula is less complex than any other known formula for the same and can be evaluated in O(logc) time, where c is a constant. It is shown that there is no closed-form formula for the above. Other variants for B(n) are described as well. Since the recurrence relation for the minimum number of comparisons of keys for MergeSort is identical with a recurrence relation for the number of 1s in binary expansions of all integers between 0 and n (exclusively), the above results extend to the sum of binary digits problem.