C++ Program to Merge two sorted arrays without using Extra space
Merge two sorted arrays without using extra space in C++
Here, in this page we will discuss the program to Merge two sorted arrays without using extra space in C++ . We are given two sorted arrays. We need to merge these two arrays such that the initial numbers (after complete sorting) are in the first array and the remaining numbers are in the second array. Extra space allowed in O(1).
Algorithm :
- Take the size of first array from the user and store it in variable say m.
- Now, declare an array of size m and take m elements of the array from the user.
- Take another variable say n to hold the size of second array and take its value from the user.
- Now, declare an array of size n and take n elements from the user.
- Now call the function merge that perform the required operations in O(1) space.
- Inside merge(),
- Iterate through every element of arr2[] starting from last element.
- Do following for every element arr2[i]
- Store last element of ar1[i]: last = arr1[i]
- Loop from last element of arr1[] while element arr1[j] is greater than arr2[i]. arr1[j+1] = arr1[j] // Move element one position ahead j–
- If any element of arr1[] was moved or (j != m-1) arr1[j+1] = arr2[i] and arr2[i] = last
Code in C++
// C++ program to merge two sorted
// arrays with O(1) extra space.
#include <bits/stdc++.h>
using namespace std;
void merge(int arr1[], int arr2[], int m, int n)
{
// Iterate through all elements
// of ar2[] starting from the last element
for (int i = n - 1; i >= 0; i--)
{
/* Find the smallest element greater than ar2[i].
Move all elements one position ahead till the
smallest greater element is not found */
int j, last = arr1[m - 1];
for (j = m - 2; j >= 0 && arr1[j] > arr2[i]; j--)
arr1[j + 1] = arr1[j];
// If there was a greater element
if (j != m - 2 || last > arr2[i])
{
arr1[j + 1] = arr2[i];
arr2[i] = last;
}
}
}
// Driver program
int main()
{
int m, n;
cin>>m;
int arr1[m];
for(int i=0; i<m; i++) cin>>arr1[i];
cin>>n;
int arr2[n];
for(int i=0; i<n; i++) cin>>arr2[i];
merge(arr1, arr2, m, n);
cout << "After Merging nFirst Array: ";
for (int i = 0; i < m; i++)
cout << arr1[i] << " ";
cout << "\nSecond Array: ";
for (int i = 0; i < n; i++)
cout << arr2[i] << " ";
return 0;
}
Output
Input :
6
1 5 9 10 15 20
4
2 3 8 13
Output :
After Merging
First Array: 1 2 3 5 8 9
Second Array: 10 13 15 20
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Login/Signup to comment