Coding Exercise – How to Merge Two Sorted Array?


Task: Merge two given sorted integer array A and B into a new sorted integer array. Example A=[1,2,3,4], B=[2,4,5,6], return [1,2,2,3,4,4,5,6]

This is the final step of the merge sort algorithm.

To merge two sorted list, we can start from the beginning or from the end (either direction is OK). We need to index pointers pointing to each array. For example, if we start from the beginning, at each iteration, we compare the values and take the smaller one and push it in the sorted array.

At the end, the remaining elements have to be pushed to the sorted array.

The complexity is O(A+B) where A and B are the length of two sorted arrays respectively.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    /**
     * @param A: sorted integer array A
     * @param B: sorted integer array B
     * @return: A new sorted integer array
     */
    vector<int> mergeSortedArray(vector<int> &A, vector<int> &B) {
        vector<int> r;
        auto a = A.size();
        auto b = B.size();
        r.reserve(a + b);
        auto i = 0, j = 0;
        while (i < a && j < b) {
            if (A[i] < B[j]) { // take the smaller one
                r.push_back(A[i ++]);
            } else {
                r.push_back(B[j ++]);
            }
        }
        // push the remaining elements to sorted array.
        for (auto k = i ; k < a; ++ k) {
            r.push_back(A[k]);
        }
        for (auto k = j ; k < b; ++ k) {
            r.push_back(B[k]);
        }
        return r;
    }
};
class Solution {
public:
    /**
     * @param A: sorted integer array A
     * @param B: sorted integer array B
     * @return: A new sorted integer array
     */
    vector<int> mergeSortedArray(vector<int> &A, vector<int> &B) {
        vector<int> r;
        auto a = A.size();
        auto b = B.size();
        r.reserve(a + b);
        auto i = 0, j = 0;
        while (i < a && j < b) {
            if (A[i] < B[j]) { // take the smaller one
                r.push_back(A[i ++]);
            } else {
                r.push_back(B[j ++]);
            }
        }
        // push the remaining elements to sorted array.
        for (auto k = i ; k < a; ++ k) {
            r.push_back(A[k]);
        }
        for (auto k = j ; k < b; ++ k) {
            r.push_back(B[k]);
        }
        return r;
    }
};

You may also like: 编程练习题 – 如何合并两个有序的数组?

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
311 words
Last Post: How do you Design a Circular FIFO Buffer (Queue) in C?
Next Post: Google's Two Egg's Problem

The Permanent URL is: Coding Exercise – How to Merge Two Sorted Array?

Leave a Reply