I have a situation where I am looping N times to sort M elements using merge sort. M can differ, i.e., depend on which N iterations we're at.

I came up with O(nmlog(m)), where n is the number of outer elements, and m is the average number of inner elements, but this doesn't sound right.

CodePudding user response：

All you can say is n times the average of mi log(mi), for which there is no simple formula. You could express this as nm*log(m*) where m* is the value that solves m*log(m*) = avg(mi log(mi)), but this is even less tractable.

As the function x log(x) is upward concave, m* will be somewhat above M:= avg(mi).

If the coefficient of variation of the mi is small, you can use the decomposition mi = M δi and take the average of (M δi) (log M log(1 δi/M)) ~ (M δi) (log M δi/M). By averaging, the terms in δi cancel out and what remains is the average of M log M δi²/M = M log M σ²/M. Hence O(NM log M Nσ²/M), which is O(NM log M).