Merge two sorted arrays in O ( 1 ) extra space using QuickSort partition | Java 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
import java . util . * ; class GFG { static 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 { int t = arr [ l ] ; arr [ l ] = brr [ r ] ; brr [ r ] = t ; l -- ; r ++ ; } } } static 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 ) ; Arrays . sort ( arr ) ; Arrays . sort ( brr ) ; for ( int i = 0 ; i < N ; i ++ ) System . out . print ( arr [ i ] + " ▁ " ) ; for ( int i = 0 ; i < M ; i ++ ) System . out . print ( brr [ i ] + " ▁ " ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 5 , 9 } ; int brr [ ] = { 2 , 4 , 7 , 10 } ; int N = arr . length ; int M = brr . length ; Merge ( arr , N , brr , M ) ; } }