## 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.

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
```