Merge two sorted arrays | Program in C, C++, java and Python

The problem, merge two sorted arrays can be done in 3 different methods. They are

Method 1: By traversing both the arrays to keep track of the current element in each arrays and finding the minimum value among the two and updating the output_array with the least value.

Method 2:  Concatenate the two arrays into one and then sorting the entire array.

Method 3: Another approach is by using min-heaps. Take first element from both the arrays and add it to the min-heap and output the root element from the min-heap to the merged_sorted_array and continue the same until all the array elements have been processed.

Method 1 to merge two sorted arrays

An easier approach to merge two sorted arrays would be by traversing both the arrays to keep track of current element in both the arrays, finding the least value among the two and updating the final array with the least value.

Algorithm

  1. Declare two arrays and input the array elements in both the arrays.
  2. Traverse both the arrays.
  3. Find the minimum element among the current two elements of both the arrays and update the output_array with the least value and increment its index to next position.

merge two sorted arrays

#include <stdio.h>
#include <stdlib.h>
int merge_two_sorted_arrays(int arr1[], int arr2[], int arr3[], int m, int n)
{
int i,j,k;
i = j = k = 0;
for(i=0;i < m && j < n;)
{
if(arr1[i] < arr2[j])
{
arr3[k] = arr1[i];
k++;
i++;
}
else
{
arr3[k] = arr2[j];
k++;
j++;
}
}
while(i < m)
{
arr3[k] = arr1[i];
k++;
i++;
}
while(j < n)
{
arr3[k] = arr2[j];
k++;
j++;
}
}
int main()
{
int n,m;
printf("\nEnter the size of Array 1 : ");
scanf("%d",&m);
printf("\nEnter the size of Array 2 : ");
scanf("%d",&n);
int arr1[m],arr2[n];
int arr3[m+n];
int i;
printf("\nInput the Array 1 elements : ");
for(i = 0; i < m; i++)
{
scanf("%d",&arr1[i]);
}
printf("\nInput the Array 2 elements : ");
for(i = 0;i<n;i++)
{
scanf("%d",&arr2[i]);
}
merge_two_sorted_arrays(arr1,arr2,arr3,m,n);
printf("\nThe Merged Sorted Array : ");
for(i = 0; i < n + m; i++)
{
printf("%d ",arr3[i]);
}
printf("\n");
return 0;
}
#include <iostream>
using namespace std;
int merge_two_sorted_arrays(int arr1[], int arr2[], int arr3[], int m, int n)
{
int i,j,k;
i = j = k = 0;
for(i=0;i < m && j < n;)
{
if(arr1[i] < arr2[j])
{
arr3[k] = arr1[i];
k++;
i++;
}
else
{
arr3[k] = arr2[j];
k++;
j++;
}
}
while(i < m)
{
arr3[k] = arr1[i];
k++;
i++;
}
while(j < n)
{
arr3[k] = arr2[j];
k++;
j++;
}
}
int main()
{
int n,m;
cout << "\nEnter the size of Array 1 : ";
cin >> m;
cout << "\nEnter the size of Array 2 : ";
cin >> n;
int arr1[m],arr2[n];
int arr3[m+n];
int i;
cout << "\nInput the Array 1 elements : ";
for(i = 0; i<m;i++)
{
cin >> arr1[i];
}
cout << "\nInput the Array 2 elements : ";
for(i = 0;i<n;i++)
{
cin>>arr2[i];
}
merge_two_sorted_arrays(arr1,arr2,arr3,m,n);
cout << "\nThe Merged Sorted Array : ";
for(i=0;i<n+m;i++)
{
cout<<arr3[i]<<" ";
}
cout << endl;
return 0;
}

Method 2 to merge two sorted arrays

In this approach, two arrays are merged into one and then the merged array is sorted finally. 

Algorithm

  1. Declare two arrays and input the array elements in both the arrays.
  2. Concatenate both the arrays.
  3. Sort the concatenated array.
#include <stdio.h>
#include<stdlib.h>
using namespace std;
int merge_arrays(int arr1[], int arr2[], int arr3[], int m, int n)
{
int i,j;
for(i = 0; i < m; i++)
{
arr3[i] = arr1[i];
}
for(i = m, j = 0 ; i < m + n; i++, j++)
{
arr3[i] = arr2[j];
}
}
int main()
{
int n,m;
printf("\nEnter the size of Array 1 : ");
scanf("%d",&m);
printf("\nEnter the size of Array 2 : ");
scanf("%d",&n);
int arr1[m],arr2[n];
int arr3[m+n];
int i;
printf("\nInput the Array 1 elements : ");
for(i = 0; i<m;i++)
{
scanf("%d",&arr1[i]);
}
printf("\nInput the Array 2 elements : ");
for(i = 0;i<n;i++)
{
scanf("%d",&arr2[i]);
}
merge_arrays(arr1,arr2,arr3,m,n);
printf("\nThe Merged Sorted Array : ");
for(i = 0; i < m+n-1; i++)
{
for(int j = 0; j < m+n-i-1; j++)
{
if(arr3[j] > arr3[j + 1])
{
int temp = arr3[j];
arr3[j ] = arr3[j + 1];
arr3[j + 1] = temp;
}
}
}
for(i = 0; i < n + m; i++)
{
printf("%d ",arr3[i]);
}
printf("\n");
return 0;
}
#include <bits/stdc++.h>
#include<algorithm>
using namespace std;
int merge_arrays(int arr1[], int arr2[], int arr3[], int m, int n)
{
int i,j;
for(i = 0; i < m; i++)
{
arr3[i] = arr1[i];
}
for(i = m, j = 0 ; i < m + n; i++, j++)
{
arr3[i] = arr2[j];
}
}
int main()
{
int n,m;
cout << "\nEnter the size of Array 1 : ";
cin >> m;
cout << "\nEnter the size of Array 2 : ";
cin >> n;
int arr1[m],arr2[n];
int arr3[m+n];
int i;
cout << "\nInput the Array 1 elements : ";
for(i = 0; i<m;i++)
{
cin >> arr1[i];
}
cout << "\nInput the Array 2 elements : ";
for(i = 0;i<n;i++)
{
cin >> arr2[i];
}
merge_arrays(arr1,arr2,arr3,m,n);
cout << "\nThe Merged Sorted Array : ";
sort(arr3, arr3 +(m+n));
for(i = 0; i < n + m; i++)
{
cout << arr3[i] << " ";
}
cout << endl;
return 0;
}

Method 3 to merge sorted arrays

Another approach is by using min-heaps. Take the first element from both the arrays and add it to the min-heap and output the root element from the min-heap to the output_array and continue the same until all the array elements have been processed.

Algorithm

  1. Declare two arrays and input the array elements in both the arrays.
  2. Take the first element from both the arrays and insert them into a min-heap.
  3. The root element of the min-heap (minimum element) is moved to the output_array and the index of the output_array is incremented.
  4. Now, take the next element from both the arrays and continue the same procedure.

Test case:

Input:
Array 1 : 2 3 6 7 9
Array 2 : 1 4 5 8 10

Output:

Merged Sorted Array : 1 2 3 4 5 6 7 8 9 10

merge two sorted arrays