Given two sorted arrays, develop logic to merge them into a third sorted array. Ideally, with O(n) complexity.

There are two ways to attack this problem.

The first-cut solution, which comes almost instantaneously to our minds, is

    1. append the two arrays [ O(n) ]
    2. sort the resulting array [ O(nlogn) ]

The complexity for this solution will be O(nlogn). Not so impressive, given the fact that we already have two re-sorted arrays.

The second approach uses the following logic:

1. First array is denoted by a1. a1[i] denotes an element in a1[i]
   Second array is denoted by a2. a2[j] denotes an element in a2[j]
2. create a new array with length = len(a1) + len(a2). Let us call this array m. An element in m is denoted by m[k].
3. if (a1[i] < a2[j]):
        m[k]=a1[i]
        m[++k]=a2[j]
        i++
   else if (a1[i] > a2[j]):
        m[k]=a2[j]
        m[++k]=a1[i]
        j++
   else :
        m[k]=a1[i]
        m[++k]=a2[j]
        i++
        j++
4. if (i==len(a1)):
        append elements j to len(a2)-1 of a2 to m
   else if (j==len(a2)):
        append elements i to len(a1)-1 of a1 to m
   else :
        goto step 3

Since the two given arrays are iterated over only once in this solution, the complexity is O(n). Where n is the length of the resulting merged array.

Advertisement