Merge Sorted Array Solutions in C++

// Source : https://oj.leetcode.com/problems/merge-sorted-array/
// Author : Hao Chen
// Date   : 2014-06-20



#include <stdio.h>

void merge(int A[], int m, int B[], int n) {
    int ia = m-1 ;
    int ib = n-1 ;
    int i = m + n - 1;
    for (int i=m+n-1; i>=0; i--){
        
        if (ia>=0 && ib<0){
            break;
        }
        if (ia<0 && ib>=0){
            A[i] = B[ib--];
            continue;
        }            
        if (ia>=0 && ib>=0){
            if (A[ia] > B[ib]){
                A[i] = A[ia--];
            }else{
                A[i] = B[ib--];
            }
        }

    }
}

void printArray(int A[], int n) {
    printf("{");
    for(int i=0; i<n; i++) {
        printf("%d, ", A[i]);
    }
    printf("}\n");
}

int main()
{
    int a[]={2,4,6,8,10,0,0,0};
    int b[]={1,3,5};
    merge(a, 5, b, 3 );
    printArray(a,  sizeof(a)/sizeof(int));

    int a1[]={2,4,0,0,0};
    int b1[]={3,5,7};
    merge(a1, 2, b1, 3 );
    printArray(a1, sizeof(a1)/sizeof(int));

    int a2[]={12,14,16,18,20,0,0,0};
    int b2[]={1,3,5};
    merge(a2, 5, b2, 3 );
    printArray(a2,  sizeof(a2)/sizeof(int));

    int a3[]={2,0};
    int b3[]={3,};
    merge(a3, 1, b3, 1 );
    printArray(a3, sizeof(a3)/sizeof(int));

    int a4[]={0,0,0};
    int b4[]={1,3,5};
    merge(a4, 0, b4, 3 );
    printArray(a4, sizeof(a4)/sizeof(int));

    int a5[]={2,4,6,8,10,0,0,0};
    int b5[]={11,13,15};
    merge(a5, 5, b5, 3 );
    printArray(a5,  sizeof(a5)/sizeof(int));

    int a6[]={2,4,0,0,0,0,0,0};
    int b6[]={1,3,5,7,9,11};
    merge(a6, 2, b6, 6 );
    printArray(a6, sizeof(a6)/sizeof(int));

    return 0;


}

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        for (int k = m+n-1, i=m-1, j=n-1; k>=0; --k)
            if (i>=0 && j>=0) A[k] = A[i] > B[j] ? A[i--] : B[j--];
            else if (j>=0) A[k] = B[j--];        
    }
};

/// Source : https://leetcode.com/problems/merge-sorted-array/
/// Author : liuyubobobo
/// Time   : 2019-02-07

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;


/// Sorting
/// Time Complexity: O(nlogn)
/// Space Complexity: O(1)
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {

        assert(nums1.size() == m + n && nums2.size() == n);

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

        sort(nums1.begin(), nums1.end());
    }
};


void print_vec(const vector<int>& vec){
    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    vector<int> nums1 = {1, 3, 5, 7};
    int m = nums1.size();

    vector<int> nums2 = {2, 4, 6};
    int n = nums2.size();

    for( int i = 0 ; i < nums2.size() ; i ++ )
        nums1.push_back(0);

    Solution().merge(nums1, m, nums2, n);
    print_vec(nums1);

    return 0;
}

/// Source : https://leetcode.com/problems/merge-sorted-array/
/// Author : liuyubobobo
/// Time   : 2016-12-06

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;


/// Standard merge process in merge sort
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {

        assert(nums1.size() == m + n && nums2.size() == n);

        for(int i = n + m - 1 ; i >= n ; i -- )
            nums1[i] = nums1[i - n];

        int i = n;  // pointer for nums1 [n, n+m)
        int j = 0;  // pointer for nums2 [0, n)
        int k = 0;  // pointer merged nums1 [0, n+m)
        while( k < n + m ){
            if( i >= n+m )
                nums1[k++] = nums2[j++];
            else if( j >= n )
                nums1[k++] = nums1[i++];
            else if( nums1[i] < nums2[j] )
                nums1[k++] = nums1[i++];
            else
                nums1[k++] = nums2[j++];
        }
    }
};


void print_vec(const vector<int>& vec){
    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    vector<int> nums1 = {1, 3, 5, 7};
    int m = nums1.size();

    vector<int> nums2 = {2, 4, 6};
    int n = nums2.size();

    for( int i = 0 ; i < nums2.size() ; i ++ )
        nums1.push_back(0);

    Solution().merge(nums1, m, nums2, n);
    print_vec(nums1);

    return 0;
}