Merging sorted arrays and finding Big O bounds

Question

Say we have $x$ amount of sorted arrays, each with $n$ elements, and we combine them one at a time. So merging the first two arrays would give us $2n$ in terms of cost, and $3n$ for the next array, all the way until $xn$ for the cost of merging. How would one go about finding the tightest possible Big-O bound for the cost of all the merges? I don't know how to go about this, I have tried writing an equation for the sequence, and that might be where I am going wrong. The sequence would look something like $2n+3n+4n \dots +kn = n(2+3+4+5+ \dots +k)$ and I'm not sure where to go next.

Answer 1

In case the order of the elements does not matter:

I assume your arrays are not sorted and you don't care of the order of the elements when you merge them.

If you store your arrays as a linked list, then merging list1 and list2 takes $O(1)$ time: you just point list1's tail to list2's head or vice versa depending how you are going to merge. So for $x$ arrays it wil take $O(x)$ time.

If you initially store them as $x$ separate static arrays (by static I mean their size is fixed and the arrays do not grow) then at each step you will need to create a new array of larger size to combine two previous arrays by copying each element one-by-one. Thus, initially it will take $2n$ steps, then $3n$ an so on. Then the total number of steps is $n(2+3+\dots + x) = n(\frac{x(1+x)}{2} - 1)$ which is $O(nx^2)$.

If your array is dynamic, i.e., you can append one element to the end of the arrays in $O(1)$ time, then you just append all elements to the first array in $O(nx)$ time.

In case the arrays are sorted and the order of the elements does matter:

The underlying structure does not provide an advantage, whether it is a linked list or dynamic array. Again assume that elements are stored as $x$ separate static arrays. Then we merge two arrays like in the Merge sort algorithm. The total number of steps is $n(2+3+\dots + x) = n(\frac{x(1+x)}{2} - 1)$ which is $O(nx^2)$.

But you could use the same procedure exactly like in the Merge sort algorithm by pairwise merging arrays at each stage. This will take $O(nx\log_2{x})$ time.