Recent content by sodiumbromate

Shouldn't it just be kn? That's what the pattern seems to suggest.

Where do you get k^2 from? Don't fully follow.

Well, merging will happen k-1 times. So the merging complexity would be (k-1)n? Which is in big theta of n? (The merging part of mergesort is linear, not logarithmic, my bad).

Homework Statement We have k >= 1 sorted arrays, each one containing n >= 1 elements (all equal length). We want to combine all of them into a single sorted array with kn elements. We have a "naive" algorithm: merge the first two arrays, then merge the third array into the result, then merge...