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?
Imagine your input size is n = 2m + k, where k < 2m.
Then you can just add as many extra values to your list as you need to make the size 2m + 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(2m + 1 log(2m + 1)) time.
Well, 2m + 1 = 2 * 2m <= 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.