Merge Two Sorted array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

Solution one: using extra space

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int index1 = 0, index2 = 0;
    vector<int> temp;
    while (index1 < m && index2 < n) {
        if (nums1[index1] < nums2[index2]) {
            temp.push_back(nums1[index1]);
            index1 += 1;
        } else {
            temp.push_back(nums2[index2]);
            index2 += 1;
        }
    }

    while (index1 < m) {
        temp.push_back(nums1[index1]);
        index1 += 1;
    }

    while (index2 < n) {
        temp.push_back(nums2[index2]);
        index2 += 1;
    }

    nums1 = temp;
}

Solution two: without extra space

If there's enough space in one of the array, then we can start merging from the end of the arrays.

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int index1 = m-1, index2 = n-1, index3 = m+n-1;
    while(index1 >= 0 && index2 >= 0) {
        nums1[index3--] = nums1[index1] > nums2[index2] ? nums1[index1--] : nums2[index2--];
    }

    while(index1 >= 0) {
        nums1[index3--] = nums1[index1--];
    }

    while(index2 >= 0) {
        nums1[index3--] = nums2[index2--];
    }
}

Solution three: without extra space

If there's no space in either of the array, then we can use the following solution, which output two sorted array, and the elements from array1 is smaller than array2.

Note: Move larger elements to array2.

The idea is to begin from last element of ar2[] and search it in ar1[]. If there is a greater element in ar1[], then we move last element of ar1[] to ar2[]. To keep ar1[] and ar2[] sorted, we need to place last element of ar2[] at correct place in ar1[]. We can use Insertion Sort type of insertion for this. Below is algorithm:

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    if(m == 0) {
        for(int i=0; i<n; i++) {
            nums1[i] = nums2[i];            
        }
        return;
    }

    for (int i=n-1; i>=0; i--) {
        int j, last = nums1[m-1];
        for (j=m-2; j>=0 && nums1[j] > nums2[i]; j--) {
            nums1[j+1] = nums1[j];
        }

        // If there was a greater element
        if (j != m-2 || last > nums2[i]) {
            nums1[j+1] = nums2[i];
            nums2[i] = last;
        }
    }

    for (int i=0; i<n; i++) {
        nums1[m+i] = nums2[i];
    }
}

results matching ""

    No results matching ""