Problem Statement:
You are given with 2 sorted arrays, you need to merge the array in-place.
You may assume that the first array will have enough space to accommodate all the array elements.
Example:
Input: arr1 = [1,2,3] arr2 = [2,5,6] Output: [1,2,2,3,5,6] According to the question, we can assume that the first array will have enough space to hold total (m+n) array elements. So arr1 = [1, 2, 3, 0, 0, 0]
The solution to this problem is very simple, below are the steps on how to do it.
We will have to do a reverse sorting, by taking the max element from arr2 and comparing with the elements from arr1.
We have: arr1 = [1,2,3,0,0,0], m = 3 arr2 = [2,5,6], n = 3 k = m+n-1 Pass 1: arr1 = [1,2,3,0,0,0] | | i k arr2 = [2,5,6] | j Now check: arr2[j]>arr1[i] thus arr1[k] = 6. Now decrement both k and j. At the end of Pass 1, array 1 will look like: arr1 = [1,2,3,0,0,6] | | i k Pass 2: arr1 = [1,2,3,0,0,6] | | i k arr2 = [2,5,6] | j arr2[j]>arr1[i] thus arr1[k] = 5. Now decrement both k and j. At the end of Pass 2, array 1 will look like: arr1 = [1,2,3,0,5,6] | | i k Pass 3: arr1 = [1,2,3,0,5,6] | | i k arr2 = [2,5,6] | j Now check: arr2[j]>arr1[i] false, so we copy the i'th element in k'th position. Now decrement both k and i. At the end of Pass 2, array 1 will look like: arr1 = [1,2,3,3,5,6] | | i k Pass 4: arr1 = [1,2,3,3,5,6] | | i k arr2 = [2,5,6] | j Now check: arr2[j]>arr1[i] thus arr1[k] = 2. Now decrement both k and j. Final array: arr1 = [1,2,2,3,5,6] The time complexity will be O(m+n).
Solution in C++
#include <vector> #include <algorithm> //visit www.ProDeveloperTutorial.com for 450+ solved questions #include <iostream> #include <queue> using namespace std; void in_place_merge(vector<int>& arr1, int m, vector<int>& arr2, int n) { int i = m-1; int j = n-1; int k = m+n-1; while(i>=0&&j>=0) { if(arr1[i]>arr2[j]) { arr1[k] = arr1[i]; i--; k--; } else { arr1[k] = arr2[j]; j--; k--; } } while(i>=0) arr1[k--]=arr1[i--]; while(j>=0) arr1[k--]=arr2[j--]; } int main() { std::vector<int> arr1 = {1, 2, 3, 0, 0, 0}; std::vector<int> arr2 = {2, 5, 6}; in_place_merge(arr1, 3, arr2, 3); cout<<"The sorted array is "<<endl; for (std::vector<int>::iterator itr = arr1.begin(); itr != arr1.end(); ++itr) { cout<<*itr; } return 0; }
Output:
The sorted array is 122356