Merge two sorted arrays in O(1) extra space using QuickSort partition

Implementation in C++

// C++ program to Merge two sorted arrays in O(1) extra space using QuickSort partition
#include <bits/stdc++.h>
using namespace std;

// Function to perform the partition

void partition(int arr[], int N, int brr[], int M, int Pivot)
{
	// Storing index of each element of arr[]
	int l = N - 1;

	// Storing index of each element of brr[]
	int r = 0;

	// Traversing the arrays
	while (l >= 0 && r < M) {

		// condition if pivot element is lesser than arr[l]
		if (arr[l] < Pivot)
			l--;

		// condition if Pivot is bigger than brr[r]
		else if (brr[r] > Pivot)
			r++;

		// otherwise
		else {
			swap(arr[l], brr[r]);
			l--;
			r++;
		}
	}
}

// Merging both two sorted arrays
void Merge(int arr[], int N, int brr[], int M)
{
	int l = 0;

	int r = 0;

	// Storing index of each element the final sorted array
	int index = -1;

	// Stores the pivot element
	int Pivot = 0;

	// Traverse both the array
	while (index < N && l < N && r < M) {

		if (arr[l] < brr[r]) {
			Pivot = arr[l++];
		}
		else {
			Pivot = brr[r++];
		}
		index++;
	}

	// If pivot element is not found || index is less than N
	while (index < N && l < N) {
		Pivot = arr[l++];
		index++;
	}

	// If pivot element is not found or index < N
	while (index < N && r < M) {
		Pivot = brr[r++];
		index++;
	}

	// Placing the first N elements of the sorted array into arr[] and the last M elements of the sorted array into brr[]
	partition(arr, N, brr, M, Pivot);

	// Sort both the arrays
	sort(arr, arr + N);

	sort(brr, brr + M);

	// Printing the first N elements

	for (int i = 0; i < N; i++)
		cout << arr[i] << " ";

	// Printing the last M elements

	for (int i = 0; i < M; i++)
		cout << brr[i] << " ";
}


int main()
{

	int N; int M; 
	cin>>N;
	cin>>M;
	int arr[N]; 
	int brr[M]; 
	for(int i=0; i<N; i++){
	    cin>>arr[i];
	}
	for(int i=0; i<M; i++){
	    cin>>brr[i];
	}
	Merge(arr, N, brr, M);

	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Sample Input: 
5 3
1 4 6 7 8
2 3 5
Sample Output:
1 2 3 4 5 6 7 8

Complexity Analysis

Time Complexity: O((N + M)*log(N + M)).

Analysing Time Complexity:

Each element in both the array is traversed once and swapped only when pivot element is greater.

Space complexity: O(1).

Also see, Euclid GCD Algorithm

FAQs

1. Which element is to be chosen as a pivot element?
   First, last or median element to be chosen as the pivot element.
    
2. What is a quick sort? 
   Divide and conquer algorithm which sorts the array by dividing the array into various partitions.
    
3. What are the benefits of using recursion?
   When we can break the problem into smaller parts, we can use recursion. It helps in reducing the complexity sometimes and makes the code smaller and readable

Key Takeaways

This article taught us how to Merge two sorted arrays in O(1) extra space using QuickSort partition by approaching the problem using a partition algorithm. We discussed its implementation using illustrations, pseudocode, and proper code.

We hope you could easily take away critical techniques like analyzing problems by walking over the execution of the examples and finding out the recursive pattern followed.

Now, we recommend you practice problem sets based on recursion to master your fundamentals. You can get a wide range of questions similar to this on Coding Ninjas Studio. 

It's not the end. Must solve the problem of similar types. 

Recommended Problem - Merge K Sorted Arrays

Happy Coding.