Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:

• Each element in the result should appear as many times as it shows in both arrays.
• The result can be in any order.

 /**  
  * Return an array of size *returnSize.  
  * Note: The returned array must be malloced, assume caller calls free().  
  */  
 void merger(int *arr, int *temp, int low, int mid, int high){  
   int i = low, j = mid + 1, k = low;  
   while(i <= mid && j <= high){  
     if(arr[i] <= arr[j]){  
       temp[k++] = arr[i++];  
     }else{  
       temp[k++] = arr[j++];  
     }  
   }  
   while(i <= mid){  
     temp[k++] = arr[i++];  
   }  
   while(j <= high){  
     temp[k++] = arr[j++];  
   }  
   for(int i = low; i <= high; i++){  
     arr[i] = temp[i];  
   }  
 }  
 void mergeSort(int *arr, int *temp, int low, int high){  
   if(low < high){  
     int mid = (low + high) / 2;  
     mergeSort(arr, temp, low, mid);  
     mergeSort(arr, temp, mid + 1, high);  
     merger(arr, temp, low, mid, high);  
   }    
 }  
 int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {  
   int *temp1 = (int *)malloc(nums1Size * sizeof(int));  
   int *temp2 = (int *)malloc(nums2Size * sizeof(int));  
   int *out = (int *)malloc((nums1Size <= nums2Size ? nums1Size : nums2Size)*sizeof(int));  
   int i, j, k;  
   mergeSort(nums1, temp1, 0, nums1Size - 1);  
   mergeSort(nums2, temp2, 0, nums2Size - 1);  
   i = 0; j = 0; k = 0;  
   while(i < nums1Size && j < nums2Size){  
     if(nums1[i] == nums2[j]){  
       out[k++] = nums1[i];  
       i++; j++;  
     }else if(nums1[i] < nums2[j]){  
       i++;  
     }else{  
       j++;  
     }  
   }  
   *returnSize = k;  
   return out;  
 }