How to merge 2 sorted arrays?

Question: We have 2 sorted arrays and we want to combine them into a single sorted array.

Input: arr1[] = 1, 4, 6, 8, 13, 25    ||     arr2[] = 2, 7, 10, 11, 19, 50
Output: 1, 2, 4, 6, 7, 8, 10, 11, 13, 19, 50

One of the simplest ways to solve this problem would be to copy both the arrays into a new array and then apply some sorting technique on them. But this method will not utilize the fact that both the arrays are already sorted.

We need to apply a different approach. Here is the algorithm that we can implement.

• Initialize two variables that serve as an index to both the arrays.
• Let i point to arr1[] and j point to arr2[].
• Compare arr[i] and arr[j]
• Add the smaller element to the new array and increase the counter.
• Repeat these steps until both counters i & j have reached the end.

Here is an implementation of the above algorithm

#include<stdio.h>

//a function to merge two arrays
//array1 is of size 'l'
//array2 is of size 'm'
//array3 is of size n=l+m
void merge(int arr1[], int arr2[], int arr3[], int l, int m, int n)
{
	//3 counters to point at indexes of 3 arrays
	int i,j,k;
	i=j=k=0;

	//loop until the array 1 and array 2 are within bounds
	while(i<l && j<m)
	{
		//find the smaller element among the two
		//and increase the counter
		if(arr1[i] < arr2[j])
		{
			arr3[k] = arr1[i];

			//increment counter of 1st array
			i++;
		}
		else
		{
			arr3[k] = arr2[j];

			//increment counter of second array
			j++;
		}

		//increase the counter of the final array
		k++;
	}

	//now fill the remaining elements as it is since they are
	//already sorted
	while(i<l)
	{
		arr3[k] = arr1[i];
		i++;
		k++;
	}
	while(j<m)
	{
		arr3[k] = arr2[j];
		j++;
		k++;
	}
}

//driver program to test the above function
int main(void)
{
	int arr1[5] = {1, 5, 9, 11, 15};
	int arr2[5] = {2, 4, 13, 99, 100};

	int arr3[10] = {0};

	merge(arr1, arr2, arr3, 5, 5, 10);

	int i=0;
	for(i=0;i<10;i++)
		printf("%d ",arr3[i]);

	return 0;
}