Merge two sorted arrays in O ( 1 ) extra space using QuickSort partition | C ++ program to implement the above approach ; Function to perform the partition around the pivot element ; Stores index of each element of the array , arr [ ] ; Stores index of each element of the array , brr [ ] ; Traverse both the array ; If pivot is smaller than arr [ l ] ; If Pivot is greater than brr [ r ] ; If either arr [ l ] > Pivot or brr [ r ] < Pivot ; Function to merge the two sorted array ; Stores index of each element of the array arr [ ] ; Stores index of each element of the array brr [ ] ; Stores index of each element the final sorted array ; Stores the pivot element ; Traverse both the array ; If pivot element is not found or index < N ; If pivot element is not found or index < N ; Place the first N elements of the sorted array into arr [ ] and the last M elements of the sorted array into brr [ ] ; Sort both the arrays ; Print the first N elements in sorted order ; Print the last M elements in sorted order ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void partition ( int arr [ ] , int N , int brr [ ] , int M , int Pivot ) { int l = N - 1 ; int r = 0 ; while ( l >= 0 && r < M ) { if ( arr [ l ] < Pivot ) l -- ; else if ( brr [ r ] > Pivot ) r ++ ; else { swap ( arr [ l ] , brr [ r ] ) ; l -- ; r ++ ; } } } void Merge ( int arr [ ] , int N , int brr [ ] , int M ) { int l = 0 ; int r = 0 ; int index = -1 ; int Pivot = 0 ; while ( index < N && l < N && r < M ) { if ( arr [ l ] < brr [ r ] ) { Pivot = arr [ l ++ ] ; } else { Pivot = brr [ r ++ ] ; } index ++ ; } while ( index < N && l < N ) { Pivot = arr [ l ++ ] ; index ++ ; } while ( index < N && r < M ) { Pivot = brr [ r ++ ] ; index ++ ; } partition ( arr , N , brr , M , Pivot ) ; sort ( arr , arr + N ) ; sort ( brr , brr + M ) ; for ( int i = 0 ; i < N ; i ++ ) cout << arr [ i ] << " ▁ " ; for ( int i = 0 ; i < M ; i ++ ) cout << brr [ i ] << " ▁ " ; } int main ( ) { int arr [ ] = { 1 , 5 , 9 } ; int brr [ ] = { 2 , 4 , 7 , 10 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int M = sizeof ( brr ) / sizeof ( brr [ 0 ] ) ; Merge ( arr , N , brr , M ) ; return 0 ; }