Merge Sort Using inplace_merge() Function

Share Your Love

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)

Share Your Love
Avatar photo
Lingaraj Senapati

Hey There! I am Lingaraj Senapati, the Founder of lingarajtechhub.com My skills are Freelance, Web Developer & Designer, Corporate Trainer, Digital Marketer & Youtuber.

Articles: 355

Newsletter Updates

Enter your email address below to subscribe to our newsletter