Method 2 (O(n1 + n2) Time and O(n1 + n2) Space) The idea is to use Merge function of Merge sort. Create an array arr3[] of size n1 + n2. Simultaneously traverse arr1[] and arr2[]. Pick smaller of current elements in arr1[] and arr2[], copy this smaller element to next position in arr3[] and move ahead in arr3[] and the array whose element is picked. If there are are remaining elements in arr1[] or arr2[], copy them also in arr3[].