# Program for Merging two Sorted Array

If there are two sorted arrays, then process of combining these sorted array into another sorted array is called merging. Let us take one example. Let us suppose \(arr_1\) and \(arr_2\) are two sorted array, Our task is to combine them into a third sorted array \(arr_3\).

## **Naive Approach for Array Merging**

A simple approach to merge the array is first copy the \(arr_1\) into \(arr_3\) and then copy the second array \(arr_2\) into \(arr_3\). After copying the two array sort the whole array \(arr_3\) by applying any sorted algorithm.

Time complexity of this approach is equal to sum of:

**Copying the two array:**if first array has \(n_1\) element and second array has \(n_2\) element, then \(\mathcal O(n_1 + n_2)\) or \(\mathcal O(n)\) where \(n = n_1 + n_2\).**Sorting the final array:**If we use quick sort then \(\mathcal O(n \log n)\).

**So total time required is =** \(\mathcal O(n) + \mathcal O(n \log n) \).

**Hence time complexity in worst case is:** \(\mathcal O(n \log n)\).

**Efficient Approach**

In the above approach we are not utilizing the fact that the both the array are sorted. Since both arrays are sorted, we can merge them efficiently by making only one pass through each array.

We will take one element from each array, compare them and then take the smaller one in the third array. This process will continue until the elements of one array are finished. Then remaining element of unfinished array are put in the third array.

Illustration of the above algorithm are shown in the below figure:

**Implementation**

Below is the implementation of above method in C.

// C program to merge two sorted arrays #include<stdio.h> #include<stdlib.h> // Merge arr1[0..n1-1] and arr2[0..n2-1] into arr3[0..n1+n2-1] void mergeArrays(int arr1[], int arr2[], int n1, int n2, int arr3[]) { int i = 0, j = 0, k = 0; // Traverse both array while (i <,n1 && j <,n2) { // Check if current element of first // array is smaller than current element // of second array. If yes, store first // array element and increment first array // index. Otherwise do same with second array if (arr1[i] < arr2[j]) arr3[k++] = arr1[i++]; else arr3[k++] = arr2[j++]; } // Store remaining elements of first array while (i < n1) arr3[k++] = arr1[i++]; // Store remaining elements of second array while (j < n2) arr3[k++] = arr2[j++]; } // Driver code int main() { int arr1[] = {1, 3, 5, 7}; int n1 = sizeof(arr1) / sizeof(arr1[0]); int arr2[] = {2, 4, 6, 8}; int n2 = sizeof(arr2) / sizeof(arr2[0]); int arr3[n1+n2]; mergeArrays(arr1, arr2, n1, n2, arr3); printf("Array after merging \n"); for (int i=0; i < n1+n2; i++) printf("%d ",arr3[i]); return 0; }

**Time Complexity**

Since we scan both the array only once, worst case time complexity of the above algorithm is \(\mathcal O(n_1 + n_2) \).

This article is contributed by Ram Kripal. If you like eLgo Academy and would like to contribute, you can mail your article to admin@elgoacademy.org. See your article appearing on the eLgo Academy page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.