- #1

zeion

- 466

- 1

## Homework Statement

Suppose that you have k >= 1 sorted arrays, each one containing n >= 1 elements, and you wish to combine them into a single sorted array with kn elements.

## Homework Equations

## The Attempt at a Solution

Can I assume that each array has a size of n elements for a worst case scenario?

Then, if I were to merge them sequentially, ie merge first two, then the third with the first two, the running time would be O(kn), since, the first two will take n comparisons, making a merged list of 2n elements, then compare to the next list of n elements takes n comparisons, and latch on the rest of the 2n list.

Does that make sense?