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!
