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: