Why is iterative k-way merge O(nk^2)?

k-way merge is the algorithm that takes as input k sorted arrays, each of size n. It outputs a single sorted array of all the elements.

It does so by using the "merge" routine central to the merge sort algorithm to merge array 1 to array 2, and then array 3 to this merged array, and so on until all k arrays have merged.

I had thought that this algorithm is O(kn) because the algorithm traverses each of the k arrays (each of length n) once. Why is it O(nk^2)?

Because it doesn't traverse each of the k arrays once. The first array is traversed k-1 times, the first as merge(array-1,array-2), the second as merge(merge(array-1, array-2), array-3) ... and so on.

The result is k-1 merges with an average size of n*(k+1)/2 giving a complexity of O(n*(k^2-1)/2) which is O(nk^2).

The mistake you made was forgetting that the merges are done serially rather than in parallel, so the arrays are not all size n.

Actually in the worst case scenario,there will be n comparisons for the first array, 2n for the second, 3n for the third and soon till (k - 1)n.
So now the complexity becomes simply

n + 2n + 3n + 4n + ... + (k - 1)n
= n(1 + 2 + 3 + 4 + ... + (k - 1))
= n((k - 1)*k) / 2
= n(k^2 - k) / 2
= O(nk ^ 2)

:-)

How about this:

Step 1: Merge arrays (1 and 2), arrays (3 and 4), and so on. (k/2 array merges of 2n, total work kn).

Step 2: Merge array (1,2 and 3,4), arrays (5,6 and 7,8), and so on (k/4 merges of 4n, total work kn).

Step 3: Repeat...

There will be log(k) such "Steps", each with kn work. Hence total work done = O(k.n.log(k)).

Even otherwise, if we were to just sort all the elements of the array we could still merge everything in O(k.n.log(k.n)) time.

> k-way merge is the algorithm that takes as input k sorted arrays, each of size n. It outputs a single sorted array of all the elements. > > I had thought that this algorithm is O(kn)

We can disprove that by contradiction. Define a sorting algorithm for m items that uses your algorithm with k=m and n=1. By the hypothesis, the sorting algorithm succeeds in O(m) time. Contradiction, it's known that any sorting algorithm has worst case at least O(m log m).

You don't have to compare items 1 by 1 each time. You should simply maintain the most recent K items in a sorted set. You remove the smallest and relace it by its next element. This should be n.log(k)

Relevant article. Disclaimer: I participated in writing it

1. You have k sorted arrays, each of size n. Therefore total number of elements = k * n

2. Take the first element of all k arrays and create a sequence. Then find the minimum of this sequence. This min value is stored in the output array. Number of comparisons to find the minimum of k elements is k - 1.

3. Therefore the total number of comparisons
   = (comparisons/element) * number of elements
   = (k - 1) * k * n
   = k^2 * n // approximately
   

A common implementation keeps an array of indexes for each one of the k sorted arrays {i_1, i_2, i__k}. On each iteration the algorithm finds the minimum next element from all k arrays and store it in the output array. Since you are doing kn iterations and scanning k arrays per iteration the total complexity is O(k^2 * n).

Here's some pseudo-code:

Input: A[j] j = 1..k : k sorted arrays each of length n
Output: B : Sorted array of length kn

// Initialize array of indexes
I[j] = 0 for j = 1..k

q = 0

while (q < kn):
	p = argmin({A[j][I[j]]}) j = 1..k 			// Get the array for which the next unprocessed element is minimal (ignores arrays for which I[j] > n)
	B[q] = A[p][I[p]]
	I[p] = I[p] + 1
	q = q + 1

1. You have k arrays each with n elements. This means total k*n elements.

2. Consider it a matrix of k*n. To add first element to the merged/ final array, you need to compare heads of k arrays. This means for one element in final array you need to do k comparisons.

So from 1 and 2, for Kn elements, total time taken is O(kk*n).

For those who want to know the details or need some help with this, I'm going expand on Recurse's answer and follow-up comment

• We only need k-1 merges because the last array is not merged with anything
• The formula for summing the terms of an arithmetic sequence is helpful; Sn=n(a1 + an)2

Stepping through the first 4 merges of k arrays with n elements

+-------+-------------------+-------------+
| Merge | Size of new array |    Note     |
+-------+-------------------+-------------+
| 1     | n+n  = 2n         | first merge  |
| 2     | 2n+n = 3n         |             |
| 3     | 3n+n = 4n         |             |
| 4     | 4n+n = 5n         |             |
| k-1   | (k-1)n+n = kn     | last merge  |
+-------+-------------------+-------------+

To find the average size, we need to sum all the sizes and divide by the number of merges (k-1). Using the formula for summing the first n terms, Sn=n(a1 + an)2, we only need the first and last terms:

• a1=2n (first term)
• an=kn (last term)

We want to sum all the terms so n=k-1 (the number of terms we have). Plugging in the numbers we get a formula for the sum of all terms

Sn = ( (k-1)(2n+kn) )/2

However, to find the average size we must divide by the number of terms (k-1). This cancels out the k-1 in the numerator and we're left with an average of size of

(2n + kn)/2

Now we have the average size, we can multiply it by the number of merges, which is k-1. To make the multiplication easier, ignore the /2, and just multiply the numerators:

  (k-1)(2n+kn)
= (k^2)n + kn - 2n

At this point you could reintroduce the /2, but there shouldn't be any need since it's clear the dominant term is (k^2)*n