In-Place Merge Sort | Set 2

0 0 5 minutes read

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>::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;
}

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 them
def 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 Sort
def 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 Code
if __name__ == '__main__':
    arr = [5, 6, 3, 2, 1, 6, 7]
 
    mergeSort(arr)
 
 # This code is contributed by Aditya Sharma

C#

// Include namespace system
using 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 them
function 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 Sort
function mergeSort(arr) {
  // Recursive function to sort the array
  mergeSortUtil(0, arr.length);
 
  // Print the sorted array
  console.log(arr.join(" "));
}
 
// Driver Code
const 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 zambiatek!