Merging two sorted arrays in C++
Merging two sorted arrays in C++
In this article, we will learn about the process of merging two sorted arrays in C++. An array is said to be sorted array only if the elements placed in the array follow a particular fashion i.e. ascending order or descending order. Merging two sorted arrays requires certain steps to be followed which are explained below.
Merging two Sorted Arrays in C++
Given two sorted arrays, one array with size m+n and the other array with size n. We will merge the n sized array into m+n sized array and print the m+n sized merged array.
Example :
Input : M[] = {1, 7, absent, absent, 124, 132, absent, 155, 200};
N[] = {2,4,152};
Output : {1, 2, 4, 7, 124, 132, 152, 155, 200}
Note:- Readers are requested to submit their codes in comment section below in different languages. Best codes will be selected and published on the website.
Algorithm
Let the arrays be M[] and N[]. Size of M[] be m+n and Size of N[] be n
1. First, move the non absent elements in M[] to the end and return the number of elements that are absent ie, store it in j
2. Start from the jth element of the array M[] and 0th element of the array N[] and compare each value of the two arrays, and store the elements in M[] in ascending order
Time Complexity
O(m+n), where m and n are sizes of the arrays .
Code Implementation for merging two sorted Arrays in C++
#include <bits/stdc++.h>
#define absent INT_MAX
using namespace std;
int transform (int M[], int n)
{
int j = n - 1;
for (int i = n - 1; i >= 0; i--)
{
if (M[i] != absent)
{
M[j] = M[i];
j--;
}
}
return (j + 1);
}
int main ()
{
int M[] = { 1, 7, absent, absent, 124, 132, absent, 155, 200 };
int N[] = { 2, 4, 152, 360 };
int sizeM = sizeof (M) / sizeof (M[0]), sizeN = sizeof (N) / sizeof (N[0]);
int no_absent = transform (M, sizeM);
int m = no_absent, n = 0;
int l = 0;
while (n < sizeN and m < sizeM)
{
if (M[m] <= N[n])
{
M[l++] = M[m++];
}
else
M[l++] = N[n++];
}
while (m < sizeM)
M[l++] = M[m++];
while (n < sizeN)
M[l++] = N[n++];
for (int i = 0; i < sizeM; i++)
cout << M[i] << " ";
return 0;
}
Output: 1 2 4 7 124 132 152 155 200
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Arrays
- Introduction to Arrays – C | C++ | Java
- Introduction to 2-D Arrays – C | C++ | Java
- Sorting of Array – C | C++ | Java
- Array Rotation – C | C++ | Java
- Reverse an array or string- C | C++ | Java
- Find pairs in array with given sum – C | C++ | Java
- Sort the array in Waveform – C | C++ | Java
- Majority Element in Array – C | C++ | Java
- Boyer-Moore’s Voting Algorithm – C | C++ | Java
- K-pairs with smallest sum in 2 arrays – C | C++ | Java
- Largest Sum Contigous SubArray – C | C++ | Java
- Maximum Average Sub-array of K length – C | C++ | Java
- Size of sub-array with max sum – C | C++ | Java
- Sub-array with given sum – C | C++ | Java
- Triplet that sum to a given value – C | C++ | Java
- Segregate 0’s and 1’s in array – C | C++ | Java
- Segregate 0’s 1’s and 2’s in array – C | C++ | Java
- Sort elements in array by frequency – C | C++ | Java
- Finding pythagorean triplets in an array – C | C++ | Java
- Reorder array using given indexes – C | C++ | Java
- Merging two sorted arrays – C | C++ | Java
- Minimum number of Merge Operations to make an Array Palindrome – C | C++ | Java
- Find Zeros to be Flipped so that number of Consecutive 1’s is maximized – C | C++ | Java
Login/Signup to comment