Merging two sorted arrays into a third one can be done in O(n)?

Question

I'm trying to merge to sorted arrays into a third sorted array , but I can't see any way to do that in O(n) , only in O(n*n) .Am I wrong ? is there a way to do that in O(n) ?

Edit :

Actually the question is a little different :

I have 2 sorted skip lists and I want to merge them into a new sorted skip list ,without changing the input (i.e. the two skip lists) .

I was thinking about :

• put the lists in two arrays

• merge the two arrays using MergeSort (this takes O(n) runtime)

• build a new skip list from the sorted array .... // I'm not sure about its runtime

any ideas ?

Regards

Solution 1

You keep two loops going, and flip between each of them as you pull values from each 'side' into the 3rd array. if arr1's values are less than the current arr2, then stuff arr1's values into arr3 until you hit equality or go 'bigger', then you flip the process and start pulling values out of arr2. And then just keep bouncing back/forth until there's nothing left in either source array.

Comes out to O(n+m), aka O(n).

Solution 2

picture two arrays one above the other:

list1=[1,2,6,10]

list2=[3,4,10]

if we start from the left and work our way to the right, comparing the items, each time we take the smallest value and put it in the third array. From the list that we took the smallest item from, we move onto its next item.

i=0,j=0
list1[i] < list2[j]
take 1
i+=1
2<3
take 2
i+=1
3<6
take 3
j+=1

etc..

until we get the final merged array [1,2,3,..]

Because selecting each element for the third array only took one move, it's basically O(N).

Solution 3

you can use two index variables for the already sorted array, and another one for the array being sorted, all initialized to 0. Now, while you haven't reached the end with any of the sorted arrays, compare the two pointed values in each iteration, take the higher (or lower, depends on your sorting) value and increment the index pointing to the value you've just used.

At the end, go through the array you havn't completed and just paste the remaining values into the merged array.

That way, you're going through the values only once, meaning O(n).