Best-case Analysis of MergeSort with an Application to the Sum of Digits Problem, A manuscript (MS) v2

الأصل · EN

An exact formula B(n) = n/2(n + 1) - ∑ ₖ₌₀ n 2ᵏ Zigzag(n2ᵏ⁺¹), where Zigzag (x) = (x - x, x - x), for the minimal 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(ᶜ) time, where c is a constant. It is shown that there is no closed-form formula for the above. Since the recurrence relation for the minimal 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.