Given an array A[] of size N, the task is to sort the array in increasing order using In-Place Merge Sort.
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:
- Create a recursive function mergeSort() that accepts the start and the end indices of the array as parameters. Now, perform the following steps:
- If size of the array is equal to 1, simply return out of the function.
- Otherwise, calculate the middle index to split the array into two subarrays.
- Recursively call mergeSort() on the left and right subarrays to sort them separately.
- Then, call the inplace_merge() function to merge the two subarrays.
- After completing the above steps, print the sorted array A[].
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>#define it vector<int>::iteratorusing namespace std;Â
// Recursive function to split the array// into two subarrays and sort themvoid 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 Sortvoid 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 Codeint main(){Â Â Â Â vector<int> arr = { 5, 6, 3, 2, 1, 6, 7 };Â
    mergeSort(arr);Â
    return 0;} |
Java
import java.util.Arrays;Â
public class MergeSort {Â
    // Recursive function to split the array    // into two subarrays and sort them    public static void mergeSortUtil(int[] arr, int left, int right) {        // Handle the base case        if (right - left <= 1) {            return;        }Â
        // Otherwise, find the middle index        int mid = left + (right - left) / 2;Â
        // Recursively sort the left subarray        mergeSortUtil(arr, left, mid);Â
        // Recursively sort the right subarray        mergeSortUtil(arr, mid, right);Â
        // Merge the two sorted arrays        merge(arr, left, mid, right);    }Â
    // Function to merge two sorted subarrays    public static void merge(int[] arr, int left, int mid, int right) {        // Create a temporary array to store the merged subarray        int[] temp = new int[right - left];Â
        // Initialize indices for the left and right subarrays        int i = left;        int j = mid;        int k = 0;Â
        // Merge the two subarrays        while (i < mid && j < right) {            if (arr[i] < arr[j]) {                temp[k++] = arr[i++];            } else {                temp[k++] = arr[j++];            }        }Â
        // Copy the remaining elements from the left subarray        while (i < mid) {            temp[k++] = arr[i++];        }Â
        // Copy the remaining elements from the right subarray        while (j < right) {            temp[k++] = arr[j++];        }Â
        // Copy the merged subarray back to the original array        for (i = left, k = 0; i < right; i++, k++) {            arr[i] = temp[k];        }    }Â
    // Function to sort the array using merge sort    public static void mergeSort(int[] arr) {        // Recursive function to sort the array        mergeSortUtil(arr, 0, arr.length);    }Â
    public static void main(String[] args) {        int[] arr = { 5, 6, 3, 2, 1, 6, 7 };Â
        mergeSort(arr);Â
      for(int i:arr)        System.out.print(i+" ");    }} |
Python3
from typing import ListÂ
# Recursive function to split the array# into two subarrays and sort themdef mergeSortUtil(arr: List[int], left: int, right: int):    # Handle the base case    if right - left <= 1:        return         # Otherwise, find the middle index    mid = left + (right - left) // 2Â
    # Recursively sort the left subarray    mergeSortUtil(arr, left, mid)Â
    # Recursively sort the right subarray    mergeSortUtil(arr, mid, right)Â
    # Merge the two sorted arrays using inplace_merge() function    arr[left:right] = sorted(arr[left:right])Â
# Function to sort the array using inplace Merge Sortdef mergeSort(arr: List[int]):    # Recursive function to sort the array    mergeSortUtil(arr, 0, len(arr))Â
    # Print the sorted array    for el in arr:        print(el, end=" ")Â
# Driver Codeif __name__ == '__main__':Â Â Â Â arr = [5, 6, 3, 2, 1, 6, 7]Â
    mergeSort(arr)Â
 # This code is contributed by Aditya Sharma |
C#
// Include namespace systemusing System;Â
Â
public class MergeSort{    // Recursive function to split the array    // into two subarrays and sort them    public static void mergeSortUtil(int[] arr, int left, int right)    {        // Handle the base case        if (right - left <= 1)        {            return;        }        // Otherwise, find the middle index        var mid = left + (int)((right - left) / 2);        // Recursively sort the left subarray        MergeSort.mergeSortUtil(arr, left, mid);        // Recursively sort the right subarray        MergeSort.mergeSortUtil(arr, mid, right);        // Merge the two sorted arrays        MergeSort.merge(arr, left, mid, right);    }    // Function to merge two sorted subarrays    public static void merge(int[] arr, int left, int mid, int right)    {        // Create a temporary array to store the merged subarray        int[] temp = new int[right - left];        // Initialize indices for the left and right subarrays        var i = left;        var j = mid;        var k = 0;        // Merge the two subarrays        while (i < mid && j < right)        {            if (arr[i] < arr[j])            {                temp[k++] = arr[i++];            }            else            {                temp[k++] = arr[j++];            }        }        // Copy the remaining elements from the left subarray        while (i < mid)        {            temp[k++] = arr[i++];        }        // Copy the remaining elements from the right subarray        while (j < right)        {            temp[k++] = arr[j++];        }        // Copy the merged subarray back to the original array        for (i = left, k = 0; i < right; i++, k++)        {            arr[i] = temp[k];        }    }    // Function to sort the array using merge sort    public static void mergeSort(int[] arr)    {        // Recursive function to sort the array        MergeSort.mergeSortUtil(arr, 0, arr.Length);    }    public static void Main(String[] args)    {        int[] arr = {5, 6, 3, 2, 1, 6, 7};        MergeSort.mergeSort(arr);        foreach (int i in arr)        {           Console.Write(i.ToString() + " ");        }    }} |
Javascript
// Recursive function to split the array// into two subarrays and sort themfunction mergeSortUtil(left, right) {  // Handle the base case  if (right - left <= 1) {    return;  }Â
  // Otherwise, find the middle index  const mid = left + Math.floor((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  // splice() function  const leftArr = arr.slice(left, mid);  const rightArr = arr.slice(mid, right);  let i = 0;  let j = 0;  let k = left;  while (i < leftArr.length && j < rightArr.length) {    if (leftArr[i] < rightArr[j]) {      arr[k] = leftArr[i];      i++;    } else {      arr[k] = rightArr[j];      j++;    }    k++;  }  while (i < leftArr.length) {    arr[k] = leftArr[i];    i++;    k++;  }  while (j < rightArr.length) {    arr[k] = rightArr[j];    j++;    k++;  }}Â
// Function to sort the array// using inplace Merge Sortfunction mergeSort(arr) {  // Recursive function to sort the array  mergeSortUtil(0, arr.length);Â
  // Print the sorted array  console.log(arr.join(" "));}Â
// Driver Codeconst arr = [5, 6, 3, 2, 1, 6, 7];mergeSort(arr);Â
// This code is contributed by akashish__ |
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.
Â
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
