In-Place Merge Sort | Set 2

Examples:

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}

Approach: The idea is to use the inplace_merge() function to merge the sorted arrays in O(1) space. Follow the steps below to solve the problem:

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

#define it vector<int>::iterator

using namespace std;

void mergeSortUtil(it left, it right)

{

if (right - left <= 1)

return;

it mid = left + (right - left) / 2;

mergeSortUtil(left, mid);

mergeSortUtil(mid, right);

inplace_merge(left, mid, right);

return;

}

void mergeSort(vector<int> arr)

{

mergeSortUtil(arr.begin(), arr.end());

for (int el : arr)

cout << el << " ";

}

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)

Alternate Approaches: Refer to the previous article for other approaches to solve this problem.

Let's block ads! (Why?)

edit