I'm aware that the time complexity of merge sort is O(nlogn), but every proof I have seen involves considering the running time of merge sort to be T(n) = 2T(n/2) O(n) for n>1, and T(n) = O(1) for n=1. However, this recursion tree proof would only work when n is a power of 2, as T(n) is only defined on integers. What would the proof be for the more general case when we don't just assume the input size is a power of 2?

CodePudding user response：

Imagine your input size is n = 2^m k, where k < 2^m.

Then you can just add as many extra values to your list as you need to make the size 2^{m 1} (padding), then sort this array and pluck your dummy values back out at the end. Now, your list indeed has the length of a power of two, so you can run mergesort the way you are used to, and in O(2^{m 1} log(2^{m 1})) time.

Well, 2^{m 1} = 2 * 2^m <= 2n, so your runtime is now O(2n log(2n)) = O(n log n).

In conclusion, padding your list with enough values to turn it into a power of two will increase it with a factor <2, so by the properties of big-O notation, it is still in the same complexity class.