Home Arrays How to merge 2 sorted arrays?

How to merge 2 sorted arrays?

by nikoo28
0 comment

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;
}
0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More