Time limit: 5000ms
Memory limit: 256mb

Description:
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

In this exercise, you are required to complete the function merge() to merge two sorted arrays into one sorted array.

The main function has been provided. 

Sample Input 1:
3
3
1 2 3 0 0 0
2 5 6

Sample Output 1:
Input the number of nums1 and nums2:
Input the integers in nums1:
Input the integers in nums2:
Merged Array: 
1 2 2 3 5 6 


Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.


Sample Input 2:
1
0
1



Sample Output 2:
Input the number of nums1 and nums2:
Input the integers in nums1:
Input the integers in nums2:
Merged Array: 
1

Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].


Sample Input 3:
0
1
0
1

Sample Output 3:
Input the number of nums1 and nums2:
Input the integers in nums1:
Input the integers in nums2:
Merged Array: 
1

Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.


Code Template:

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

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    /*
        Fill in your code here.
        You can add some variables but no additional array.
    */
}


int main() {
    int m,n, *nums1, *nums2;
    printf("Input the number of nums1 and nums2:\n");
    scanf("%d",&m);
    scanf("%d",&n);
    nums1 = (int*)malloc(sizeof(int)*(m+n));
    nums2 = (int*)malloc(sizeof(int)*n);
    printf("Input the integers in nums1:\n");
    for(int i=0; i<m+n; i++)
        scanf("%d", &nums1[i]);
    printf("Input the integers in nums2:\n");
    for(int i=0; i<n; i++)
        scanf("%d", &nums2[i]);

    int nums1Size = sizeof(nums1) / sizeof(nums1[0]);
    int nums2Size = n;
		
    merge(nums1, nums1Size, m, nums2, nums2Size, n);

    printf("Merged Array: \n");
    for(int i = 0; i < m+n; i++)
        printf("%d ", nums1[i]);

    return 0;
}