Merging two sorted arrays in C++

March 21, 2023

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 .

Sort elements in array by frequency

Finding pythagorean triplets in an array

Reorder array using given indexes

Minimum number of Merge Operations to make an Array Palindrome

Find Zeros to be Flipped so that number of Consecutive 1’s is maximized

Code Implementation for merging two sorted Arrays in C++

Run

#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

Checkout list of all the video courses in PrepInsta Prime Subscription

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