#include <iostream>
using namespace std;

int * Merge (int a[], int size_a, int b[], int size_b);

int main() {
    int a[] = {1, 5, 8, 9, 13};
    int b[] = {2, 6};

    int * c = Merge(a, 5, b, 2);
    for(int i = 0; i < 7; i++) {
        cout << c[i] << " ";
    }

    cout << endl;
}

int * Merge (int a[], int size_a, int b[], int size_b) {

    // new array the combined size of the two previous ones
    int * c = new int[size_a + size_b];

    //indexes so we don't fuck around with pointer math
    int index_a = 0, index_b = 0, index_c = 0;

    while ((index_a < size_a) && (index_b < size_b)) {

        if (a[index_a] < b[index_b]) {
            c[index_c] = a[index_a];
            index_a++;
        } else {
            c[index_c] = b[index_b];
            index_b++;
        }
        index_c++;
    }

    while (index_a < size_a) {
        c[index_c] = a[index_a];
        index_a++;
        index_c++;
    }

    while (index_b < size_b) {
        c[index_c] = b[index_b];
        index_b++;
        index_c++;
    }

    return c;
}