Merging two sorted arrays in C

Merging two sorted array 

Here, in this page we will discuss the C program for merging two  sorted array. For this we will create an another array and insert the elements in efficient manner from the given two arrays.

Example: n1 = 4, Arr1[4]={2, 5, 6, 9}

                  n2 = 3, Arr2[3]={1, 7, 8}

                  then, Arr3[7]={1, 2, 5, 6, 7, 8, 9}

Merge two sorted array in C

Algorithm :

 

  • Take the size of array 1 from the user and store it in variable n1.
  • Input n1 elements from the user and store it in array arr1.
  • Take the size of array 2 from the user and store it in variable n2.
  • Input n2 elements from the user and store it in array arr2.
  • Declare an array of size n1+n2 and named it as arr3.
  • Set one pointer at arr1 and another at arr2.
  • Now, simultaneously traverse arr1 and arr2. Which element is smaller, copy that element in arr3 and move ahead.
  • After the above step and traverse the remaining elements of arr1 or arr2 and copy them in arr3.

Code based on above algorithm in C

#include<stdio.h>

void merge(int arr1[], int arr2[], int n1, int n2, int arr3[])
{
int i = 0, j = 0, k = 0;

while (i<n1 && j <n2)
{
if (arr1[i] < arr2[j])
arr3[k++] = arr1[i++];
else
arr3[k++] = arr2[j++];
}

while (i < n1)
arr3[k++] = arr1[i++];

while (j < n2)
arr3[k++] = arr2[j++];
}

int main()
{

int n1;
scanf("%d", &n1);

int arr1[n1];
for(int i=0; i<n1; i++)
scanf("%d", &arr1[i]);

int n2;
scanf("%d", &n2);

int arr2[n2];
for(int i=0; i<n2; i++)
scanf("%d", &arr2[i]);

int arr3[n1+n2];
merge(arr1, arr2, n1, n2, arr3);

printf("Array after merging\n");
for (int i=0; i < n1+n2; i++)
printf("%d ", arr3[i]);

return 0;
}
Output :

4

2 4 5 7

3

1 3 6

Array after merging :

1 2 3 4 5 6 7