O notation and merging two already sorted arrays

Question

I've been told to merge two already sorted arrays, of different sizes, A and B into an array, C in linear time.

By linear time, I understood that the time complexity of this algorithm has to be O(n). Later on, I was also told to perform sorting while merging the arrays.

One idea I had was to create an algorithm where you have two pointers in both arrays, pointing at the smallest element. The smallest element which is pointed at would go into the new array. When one array is exhausted, the remaining elements of the other array are copied into the new array.

Since I just started programming a few months ago, I have found this difficult to implement and hence I decided to perform Merge Sort (MS) since it's the most similar to the above-mentioned algorithm. However, I'm concerned with the time complexity of MS itself - O(nlogn)

However, given that the two arrays would be already sorted, would the time complexity for MS be reduced or will it remain the same?

Thanks in advance.

Answer 1

Your task is to implement the merge phase of the mergesort algorithm. mergesort has a complexity of O(N.log(N)) to sort the dataset, but each merge phase takes linear time proportional to the length of the merged set.

Here is pseudo code for this:

merge(array a, array b into array c)
    int i = 0, j = 0, k = 0;
    while (i < len(a) and j < len(b)) {
        if (a[i] <= b[j]) {
            c[k++] = a[i++];
        } else {
            c[k++] = b[j++];
        }
    }
    while (i < len(a)) {
        c[k++] = a[i++];
    }
    while (j < len(b)) {
        c[k++] = b[j++];
    }
}

The complexity is linear as each step in each of the loops copies an element into the c array, for a total of len(a) + len(b) steps.