// Arup Guha
// 1/24/2024
// Solution to COP 3502H Exam 1 Question 7

#include <stdio.h>
#include <stdlib.h>

int* setunion(int* set1, int n, int* set2, int m);

int main() {

    // Example from test.
    int arr1[4] = {2, 3, 6, 12};
    int arr2[6] = {1, 2, 6, 8, 12, 14};

    // Test it.
    int* ans = setunion(arr1, 4, arr2, 6);
    for (int i=0; i<7; i++)
        printf("%d ", ans[i]);
    free(ans);

    return 0;
}

int* setunion(int* set1, int n, int* set2, int m) {

    // This is enough space...
    int* res = calloc(n+m, sizeof(int));

    // i is index into set1, j into set2, k into res.
    int i = 0, j = 0, k = 0;

    // Go till we finish with both.
    while (i<n || j<m) {

        // Must take from set 1 only.
        if (j==m || (i<n && set1[i]<set2[j]))
            res[k++] = set1[i++];

        // Must take from set 2 only.
        else if (i==n || (j<m && set2[j]<set1[i]))
            res[k++] = set2[j++];

        // Equal case, take one copy advance both indexes.
        else {
            res[k++] = set1[i++];
            j++;
        }
    }

    // Fix size...
    res = realloc(res, k*sizeof(int));
    return res;
}