Is there a different in the number of comparisons between merge sort in different case ? For example ,

Case 1 : if I divide the array 2 parts and same size T(n)=T(n/2) T(n/2) n/2 n/2-1=T(n/2) T(n/2) n-1

Case 2 : T(n)=T(n/4) T(3n/4) (n/4) (3n/4)-1=T(n)=T(n/4) T(3n/4) n-1

Since for merging 2 sub-array(let's say length m,n) I have to make at least m n-1 comparisons, then I think the answer is yes but I am not sure.

And what's about dividing the array into $k$ sub-arrays in each iteration?

Is there a an optimal dividing for getting the lowest number of comparisons ?

I hope this is not a silly question, thanks!

CodePudding user response：

You get the best possible worst-case performance from dividing the array into equal-size parts. Consider the opposite in the extreme case: letting one part be size 1 and the other n-1. That gives you linear recursion depth, and quadratic time.

You get n log n (plus/minus some constant) k-way comparisons if you split into k subarrays of size as close to n/k as possible, where log is the base-k logarithm. Note, however, that logarithms of different bases differ only by a constant factor, so you always get O(n log n) as long as k is a constant.