Counting Merge-Sort Calls, Merges, and Comparisons

Model one run of merge sort as a recursion tree with n leaves: there are n-1 internal (splitting) nodes, so merge is called n-1 times, total mergesort invocations are 2n-1, and the worst-case element comparisons are at most n*ceil(log2 n) - 2^ceil(log2 n) + 1. Don't confuse 'total calls' with 'recursive calls'.