What is the running time of this algorithm?

zeion

1. The problem statement, all variables and given/known data

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.


2. Relevant equations



3. 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?

NascentOxygen

okay
What if there is no "rest"? Maybe the n list has elements to be slotted throughout the 2n list?

zeion

So you're saying, if the third list had more than 2n elements?
Then I would compare 2n times and latch on the left over from the third list?

I'm not sure how to set up the problem for a worst case since each array can have n >= 1 elements?

rcgldr

Are you sure it only takes n compares to merge two arrays of size n? Take a very simple case, how many compares does it take to merge 2 lists with 2 elements each, for example {1, 3} {2, 4}? What about 2 lists, 3 elements each, for example {1, 3, 5} {2, 4, 6}?

NascentOxygen

ask.com is an invaluable resource you should get to know, zeion.

http://www.ask.com/web?q=how+many+comparisons+to+merge+two+sorted+lists%3F&search=&qsrc=0& o=0&l=dir

zeion

So for the second example, I would compare 1 and 2, then insert the smaller one, then insert the larger one: (1, 2)

Then compare the next two, 3 and 4 and insert in the same way: (1, 2, 3, 4)
Then compare 5 and 6 and get (1,2,3,4,5,6)

So I compared 3 sets of 2 numbers.

rcgldr

Using this same method how would you merge {1, 2, 5} and {3, 4, 6}? By "insert" do you mean to "insert" into the output array? If so that's not a merge, and if insertion was used, the insertion would take more compares.

zeion

Okay so, to "merge" two lists I will simply append either one after the other.
This will take k - 1 appends? Or do I have say that I append each element at a time, so that would take n(k - 1) ?

Then, I suppose I will use a merge sort algorithm to sort the whole list.. which takes worst-case O(nlogn) ?

rcgldr

That's the time it takes to sort a single unsorted array of n elements, and O(...) is a relative number, the (n log n) shows how the number of elements affects O(...), without separating moves and compares (there are fewer compares than moves).

In this case, you have k sorted arrays of n elements each. I'm not sure what your supposed to calculate at "running time", the number of compares and moves as separate counts or the relative overhead versus k and n.

Maybe one more example, merge {1, 2, 9, 10} , {4, 5, 8, 11}, {3, 6, 7, 12}. How many compares do you need? How many moves do you need? What if you merged all 3 arrays in one pass?

zeion

What is a "move"?

So for the example, I would "compare" the 1 with 4.
Then, I will "move" the 4 between the 1 and the 2?
Do I also need to "move" all of 2, 9, 10 forward to make space?

The questions says, "What is the worst-case running time of this algorithm, as a function of k and n?" The algorithm being to merge the first list with the second, then that one with the third.. etc.

rcgldr

OK, apparently merging wasn't explained to you properly in class. A merge of k arrays, each of of size n, ends up copying the data into a new single array of size k x n. So there's a total of k+1 arrays involved, the k input arrays of size n each, and the output array of size k x n.

zeion

Okay so,
I think, for comparing two arrays, I would always have to compare the size of the bigger array.

So for the first method of combining the first two, then with the third etc..
It would take n compares for the first two, then 2n compares for the third with the first two, then 3n, then 4n ...

Each time I finish comparing I would move the element to the kn array, so the moves would be 2n moves for the first two, n moves for all the other ones, so total of k moves.

Does that make sense?

rcgldr

How many compares would you have to do to merge {1, 2, 9} and {3, 4, 5, 6, 7, 8}?

If you merged 2 arrays into an output array, you would need another array to merge that output array with the 3rd input array, alternating between the two output arrays. That would require (2 + 3 + ... + k) x n moves.

If you merged all k arrays in on pass, it would only take k x n moves. If you did merge k arrays in one pass, and assuming you haven't reached the end of any of the k arrays, how many compares would it take for each element moved to the single output array of size k x n?