# Merge Sort Using inplace_merge() Function

In this post, solve the merge sort using the inplace_merge() function. Given an arrayA[] 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) 