Merging two sorted arrays into a third one can be

问题:

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

回答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).

回答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).

回答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).

回答4:

Hint: consider only the head elements of both lists (and remove them [virtually] when processed).

回答5:

If both input lists are already sorted, how could the merge be O(n*n)? The algorithm given by yourself (the 3 steps) is definitely O(n) rather than O(n*n). Each step is O(n), so overall it is O(n). The big-O is determined by the highest order of your algorithm. Be sure to understand the concept of big-O before working on your homework.

回答6:

Yes it can be done, actually it would be O(n + m) where n and m are length of first and second arrays, consecutively.

The algorithm is called one pass merge

Pseudo code:

i, j, k = 0 // k is index for resulting array
//maximum length of the resulting array can be n+m, 
//so it is always safe to malloc for such a length if you are in C or C++

while(i< len(array1) and j < len(array2) )
     if (array1[i] == array2[j])
           result[k] = array1[i]
           ++i, ++j, ++k
     else if (array1[i] < array2[j])
           result[k] = array1[i]
           ++i, ++k
     else
           result[k] = array2[j] 
           ++j, ++k

//now one array might not be traversed all the way up
if ( i < len(array1) )
      while( i != len(array1))
            result[k] =  array1[i]
            ++i, ++k

else if ( j < len(array2) )
      while( j != len(array2) )
            result[k] = array2[j]
            ++j, ++k

Basically, you traverse both arrays at the same time and if the lengths are different, larger array won't be traversed all the way up, so you just add all the elements of the larger array to the result.