Merge Sort Algorithm

Problem:  Given an array of size n, sort the array using Merge Sort.

Examples:

Example 1:
Input: N=5, arr[]={4,2,1,6,7}
Output: 1,2,4,6,7,


Example 2:
Input: N=7,arr[]={3,2,8,5,1,4,23}
Output: 1,2,3,4,5,8,23

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution : 

Intuition: 

-> Merge Sort is a divide and conquers algorithm, it divides the given array into equal parts and then merges the 2 sorted parts. 

-> There are 2 main functions : 

  1. Merge() : This function is used to merge the 2 halves of the array . It assumes that both part of the array are sorted and merges both of them
  2. MergeSort() : This function divides the array into 2 parts . L to Miid and Mid+1 to R where,

  L = leftmost index of array

  R = rightmost index of array

  Mid = Middle index of array 

-> We recursively split the array, go from top-down until all sub-arrays size becomes 1.

Approach : 

-> We will be creating 2 functions mergeSort() and merge()

-> In mergeSort(), we will divide the array around the middle element by making the recursive call :

1.mergeSort(arr,l,mid)   2. mergeSort(arr,mid+1,r)    

 where l = leftmost index of array, r = rightmost index of array , mid = middle index of array

-> In merge(),  we will use a temporary array named temp. This will be used to store elements in sorted order from both the arrays which we divided.

->From the temporary array, we will return back the elements in the original array.

-> Now , let   i = leftmost index of array, j = mid+1 index of array , f = leftmost index of array ( this index will be used to store elements in the original array ) 

-> While i<= mid && j <= r , we will store elements from both the parts in temporary array in sorted manner 

-> Finally will transfer all elements from the temporary array to the original array.

-> The red number shows an order of the steps in recursion calls

Code:

C++ Code

#include <bits/stdc++.h>
using namespace std  ;

class Solution {
public:
    void merge(int arr[], int l, int mid, int r)
    {
        int i = l ;        // starting index of left half of arr
        int j = mid + 1;   // starting index of right half of arr
        int f = l ;        // index used to transfer elements in temporary array
        int temp[100000] ; // temporary array

        //storing elements in the temporary array in a sorted manner//

        while (i <= mid && j <= r) {
            if (arr[i] < arr[j]) {
                temp[f] = arr[i]  ;
                i++ ;
            }
            else {
                temp[f] = arr[j]  ;
                j++ ;
            }
            f++ ;
        }

        // if elements on the left half are still left //

        if (i > mid) {
            while (j <= r) {
                temp[f] = arr[j]  ;
                f++ ; j++ ;
            }
        }
        else {
            //  if elements on the right half are still left //
            while (i <= mid) {
                temp[f] = arr[i]  ;
                f++ ; i++ ;
            }
        }

        // transfering all elements from temporary to arr //
        for (int f = l ; f <= r; f++) {
            arr[f] = temp[f] ;
        }
    }
    void mergeSort(int arr[], int l, int r)
    {
        if (l < r) {
            int mid = (l + r) / 2 ;
            mergeSort(arr, l, mid)  ;  // left half
            mergeSort(arr, mid + 1, r)  ; // right half
            merge(arr, l, mid, r)  ;  // merging sorted halves
        }
    }
};
int main() {

    int arr[] = {9, 4, 7, 6, 3, 1, 5}  ;
    int n = 7;

    Solution obj ;
    cout << "Before Sorting Array: "<<endl;
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " "  ;
    }
    cout<<endl;
    obj.mergeSort(arr, 0, n - 1);
    cout << "After Sorting Array: "<<endl;
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " "  ;
    }
    return 0 ;
}

Output:

Before Sorting Array:
9 4 7 6 3 1 5
After Sorting Array:
1 3 4 5 6 7 9

Time complexity: O(nlogn) 

Reason: At each step, we divide the whole array, for that logn and we assume n steps are taken to get sorted array, so overall time complexity will be nlogn

Space complexity: O(n)  

Reason: We are using a temporary array to store elements in sorted order.

Auxiliary Space Complexity: O(n)

Java Code

import java.util.*;

class MergeSortClass {

       void mergeSort(int arr[], int l, int r) {
              if (l < r) {
                     int mid = (l + r) / 2;
                     mergeSort(arr, l, mid); // left half
                     mergeSort(arr, mid + 1, r); // right half
                     merge(arr, l, mid, r); // merging sorted halves
              }
       }

       void merge(int arr[], int l, int mid, int r) {
              int i = l; // starting index of left half of arr
              int j = mid + 1; // starting index of right half of arr
              int f = l; // index used to transfer elements in temporary array
              int temp[] = new int[100000]; // temporary array

              // storing elements in the temporary array in a sorted manner//

              while (i <= mid && j <= r) {
                     if (arr[i] < arr[j]) {
                            temp[f] = arr[i];
                            i++;
                     } else {
                            temp[f] = arr[j];
                            j++;
                     }
                     f++;
              }

              // if elements on the left half are still left //

              if (i > mid) {
                     while (j <= r) {
                            temp[f] = arr[j];
                            f++;
                            j++;
                     }
              } else {
                     // if elements on the right half are still left //
                     while (i <= mid) {
                            temp[f] = arr[i];
                            f++;
                            i++;
                     }
              }

              // transfering all elements from temporary to arr //
              for (f = l; f <= r; f++) {
                     arr[f] = temp[f];
              }
       }
}

class Solution {

       public static void main(String args[]) {
              Scanner sc = new Scanner(System.in);
              int n = 7;
              int arr[] = { 9, 4, 7, 6, 3, 1, 5 };
              System.out.println("Before sorting array: ");
              for (int i = 0; i < n; i++) {
                     System.out.print(arr[i] + " ");
              }
              System.out.println();
              MergeSortClass obj = new MergeSortClass();
              obj.mergeSort(arr, 0, n - 1);
              System.out.println("After sorting array: ");
              for (int i = 0; i < n; i++) {
                     System.out.print(arr[i] + " ");
              }
       }
}

Output:

Before Sorting Array:
9 4 7 6 3 1 5
After Sorting Array:
1 3 4 5 6 7 9

Time complexity: O(nlogn) 

Reason: At each step, we divide the whole array, for that logn and we assume n steps are taken to get sorted array, so overall time complexity will be nlogn

Space complexity: O(n)  

Reason: We are using a temporary array to store elements in sorted order.

Auxiliary Space Complexity: O(n)

Special thanks to Shreyas Vishwakarma for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article