In this post, solve the merge sort using **the inplace_merge()** function. Given an array**A[] **of size **N**, the task is to sort the array in increasing order using In-Place Merge Sort.

**Example:**

```
Input: A = {5, 6, 3, 2, 1, 6, 7}
Output: {1, 2, 3, 5, 6, 6, 7}
Input: A = {2, 3, 4, 1}
Output: {1, 2, 3, 4}
```

**Steps To Solve:**

The objective is to merge the sorted arrays in O(1) space using the inplace_merge() technique. To address the problem, follow the instructions below::

- Make a recursive function mergeSort() that takes the array’s start and end indices as inputs. Execute the following actions now:
- If the array’s size is equal to 1, the function should be exited.
- Otherwise, divide the array into two subarrays by calculating the centre index.
- To sort the left and right subarrays individually, execute mergeSort() recursively.
- Then, to merge the two subarrays, use the inplace merge() function.
- Print the sorted array A[ ] after you’ve completed the previous stages.

Below is the implementation of the above approach:

// C++ program for the above approach #include <bits/stdc++.h> #define it vector<int>::iterator using namespace std; // Recursive function to split the array // into two subarrays and sort them void mergeSortUtil(it left, it right) { // Handle the base case if (right - left <= 1) return; // Otherwise, find the middle index it mid = left + (right - left) / 2; // Recursively sort // the left subarray mergeSortUtil(left, mid); // Recursively sort // the right subarray mergeSortUtil(mid, right); // Merge the two sorted arrays using // inplace_merge() function inplace_merge(left, mid, right); return; } // Function to sort the array // using inplace Merge Sort void mergeSort(vector<int> arr) { // Recursive function to sort the array mergeSortUtil(arr.begin(), arr.end()); // Print the sorted array for (int el : arr) cout << el << " "; } // Driver Code int main() { vector<int> arr = { 5, 6, 3, 2, 1, 6, 7 }; mergeSort(arr); return 0; }

**Output:**

```
1 2 3 5 6 6 7
```

**Time Complexity:** O(N * log(N))**Auxiliary Space:** O(1)