Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example 
2.
Approach
2.1.
PseudoCode
3.
Implementation in C++
3.1.
Complexity Analysis
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

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

Author Urwashi Priya
0 upvote

Introduction

In this blog, we will discuss an array problem asked frequently in Interviews.

The problem is to Merge two sorted arrays in O(1) extra space using QuickSort partition.

Problem Statement

We are given two arrays, say N integers in the first array and M integers in the second array and both arrays are given in sorted order, we need to merge both the sorted arrays and print the resultant array which should be sorted.

Sample Example 

Given a sorted arr[] consisting of 5 elements: 1, 4, 6, 7, 8.
Given another sorted array brr[] consisting of 3 elements: 2, 3, 5
Merging both the sorted arrays to form an array in sorted order, we get:
1, 2, 3, 4, 5, 6, 7, 8
Generally, we can merge two sorted arrays in the following manner: merging. 
But here, according to our problem statement, we need to do this using quicksort algorithm, and no extra space is taken.

Approach

The approach to Merge two sorted arrays in O(1) extra space using QuickSort partition.

Declare the function for partition.

Declare a variable to store the index for each element of both the array.

Start traversing both the array.

If the pivot element is smaller than the first array, decrement.

If the pivot element is greater than the second array, increment.

Else swap indexes. Both increment and decrement operations are to be formed.

Merge both the array.

Till now, I assume you must have got the basic idea of what has been asked in the problem statement. So, I strongly recommend you first give it a try.

try here

Please have a look at the algorithm, and then again, you must give it a try.

PseudoCode

Algorithm

___________________________________________________________________
Procedure partition(int arr[], int N, int brr[], int M, int Pivot):
___________________________________________________________________
1.  l = N - 1, r = 0
2.  while (l >= 0 && r < M) :
          if (arr[l] < Pivot) l–
          else if (brr[r] > Pivot) r++
          Else: swap(arr[l], brr[r]); l--; r++;
3. Merge both the array.
end procedure
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

 

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.

Previous article
Count Negative Numbers in a Sorted Matrix
Next article
Longest Substring with At Least K Repeating Characters
Live masterclass