MergeSort_GreatLearning
  1. What is Merge sort
  2. Pseudocode for Merge sort
  3. Merge sort Algorithm
  4. Merge sort Algorithm Dry Run
  5. Time complexity of Merge sort
  6. Space complexity of Merge sort
  7. Merge sort program in C
  8. Merge sort in Java
  9. Merge sort in C++
  10. Merge sort in Python
  11. Merge sort example
  12. Difference between Quick sort and Merge sort

What is Merge sort

Merge sort is one of the most efficient sorting techniques and it’s based on the “divide and conquer” paradigm.

  • In merge sort, the problem is divided into two subproblems in every iteration.
  • Hence efficiency is increased drastically.
  • It follows the divide and conquer approach
    • Divide break the problem into 2 subproblem which continues until the problem set is left with one element only
    • Conquer basically merges the 2 sorted arrays into the original array

Pseudocode for MergeSort 

  • Declare left and right var which will mark the extreme indices of the array
  • Left will be assigned to 0 and right will be assigned to n-1
  • Find mid = (left+right)/2
  • Call mergeSort on (left,mid) and (mid+1,rear)
  • Above will continue till left<right
  • Then we will call merge on the 2 subproblems

Merge sort Algorithm

MergeSort(arr, left, right):
    if left > right 
        return
    mid = (left+right)/2
    mergeSort(arr, left, mid)
    mergeSort(arr, mid+1, right)
    merge(arr, left, mid, right)
end

Merge sort Algorithm Dry Run

merge sort

Time Complexity of Merge sort 

  • In the worst case, in every iteration, we are dividing the problem into further 2 subproblems. Hence this will perform log n operations and this has to be done for n iteration resulting in n log n operations total. 
  • In the best case that is sorted array, we can do some modification by using a flag to check whether the lament is already sorted or not
  • Best Time Complexity: O(nlogn)
  • Average Time Complexity: O(nlogn)
  • Worst Time Complexity: O(nlogn)

Space Complexity of Merge sort 

  • n auxiliary space is required in Merge Sort implementation as all the elements are copied into an auxiliary array
  • Hence space complexity is: O(n)

Merge sort program in C 

#include <stdio.h>

void merge(int arr[], int start, int mid, int end) {

  int len1 = mid - start + 1;
  int len2 = end - mid;

  int leftArr[len1], rightArr[len2];

  for (int i = 0; i < len1; i++)
    leftArr[i] = arr[start + i];
  for (int j = 0; j < len2; j++)
    rightArr[j] = arr[mid + 1 + j];

  int i, j, k;
  i = 0;
  j = 0;
  k = start;

  while (i < len1 && j < len2) {
    if (leftArr[i] <= rightArr[j]) {
      arr[k] = leftArr[i];
      i++;
    } else {
      arr[k] = rightArr[j];
      j++;
    }
    k++;
  }

  while (i < len1) {
    arr[k] = leftArr[i];
    i++;
    k++;
  }

  while (j < len2) {
    arr[k] = rightArr[j];
    j++;
    k++;
  }
}

void mergeSort(int arr[], int start, int end) {
  if (start < end) {

    int mid = start + (end - start) / 2;
    mergeSort(arr, start, mid);
    mergeSort(arr, mid + 1, end);
    merge(arr, start, mid, end);
  }
}

void display(int arr[], int size) {
  for (int i = 0; i < size; i++)
    printf("%d ", arr[i]);
  printf("\n");
}

int main() {
  int arr[] = {6, 5, 12, 10, 9, 1};
  int size = sizeof(arr) / sizeof(arr[0]);
  
  printf("Original array\n");
  display(arr, size);
  
  mergeSort(arr, 0, size - 1);

  printf("Sorted array\n");
  display(arr, size);
}

Output of the program:
 Original array
 6 5 12 10 9 1 
 Sorted array
 1 5 6 9 10 12 

Click here to know Quick Sort Algorithm using C , C++, Java, and Python

Merge sort in Java

class MergeSort {

  void merge(int arr[], int left, int mid, int right) {

    int len1 = mid - left + 1;
    int len2 = right - mid;

    int leftArr[] = new int[len1];
    int rightArr[] = new int[len2];

    for (int i = 0; i < len1; i++)
      leftArr[i] = arr[left + i];
    for (int j = 0; j < len2; j++)
      rightArr[j] = arr[mid + 1 + j];

    int i, j, k;
    i = 0;
    j = 0;
    k = left;

    while (i < len1 && j < len2) {
      if (leftArr[i] <= rightArr[j]) {
        arr[k] = leftArr[i];
        i++;
      } else {
        arr[k] = rightArr[j];
        j++;
      }
      k++;
    }

    while (i < len1) {
      arr[k] = leftArr[i];
      i++;
      k++;
    }

    while (j < len2) {
      arr[k] = rightArr[j];
      j++;
      k++;
    }
  }

  void mergeSort(int arr[], int start, int right) {
    if (start < right) {

      int mid = (start + right) / 2;

      mergeSort(arr, start, mid);
      mergeSort(arr, mid + 1, right);

      merge(arr, start, mid, right);
    }
  }

  static void display(int arr[]) {
    int n = arr.length;
    for (int i = 0; i < n; ++i)
      System.out.print(arr[i] + " ");
    System.out.println();
  }

  public static void main(String args[]) {
    int arr[] = { 6, 5, 12, 10, 9, 1 };

    MergeSort ob = new MergeSort();
    
    System.out.println("Original array");
    display(arr);    
    
    ob.mergeSort(arr, 0, arr.length - 1);

    System.out.println("Sorted array");
    display(arr);
  }
}


Output of the program:
 Original array
 6 5 12 10 9 1 
 Sorted array
 1 5 6 9 10 12 

Merge sort in C++ 

#include <iostream>
using namespace std;

void merge(int arr[], int start, int mid, int end) {
  
  int len1 = mid - start + 1;
  int len2 = end - mid;

  int leftArr[len1], rightArr[len2];

  for (int i = 0; i < len1; i++)
    leftArr[i] = arr[start + i];
  for (int j = 0; j < len2; j++)
    rightArr[j] = arr[mid + 1 + j];

  int i, j, k;
  i = 0;
  j = 0;
  k = start;

  while (i < len1 && j < len2) {
    if (leftArr[i] <= rightArr[j]) {
      arr[k] = leftArr[i];
      i++;
    } else {
      arr[k] = rightArr[j];
      j++;
    }
    k++;
  }

  while (i < len1) {
    arr[k] = leftArr[i];
    i++;
    k++;
  }

  while (j < len2) {
    arr[k] = rightArr[j];
    j++;
    k++;
  }
}

void mergeSort(int arr[], int start, int end) {
  if (start < end) {
    int mid = start + (end - start) / 2;

    mergeSort(arr, start, mid);
    mergeSort(arr, mid + 1, end);

    merge(arr, start, mid, end);
  }
}

void display(int arr[], int size) {
  for (int i = 0; i < size; i++)
    cout << arr[i] << " ";
  cout << endl;
}

int main() {
  int arr[] = {6, 5, 12, 10, 9, 1};
  int size = sizeof(arr) / sizeof(arr[0]);

  cout << "Original array \n";
  display(arr, size);  
  
  mergeSort(arr, 0, size - 1);

  cout << "Sorted array \n";
  display(arr, size);
  return 0;
}
Output of the program:
 Original array 
 6 5 12 10 9 1 
 Sorted array 
 1 5 6 9 10 12 

Merge sort in Python

def mergeSort(arr):
    if len(arr) > 1:

        r = len(arr)//2
        leftArr = arr[:r]
        rightArr = arr[r:]

        mergeSort(leftArr)
        mergeSort(rightArr)

        i = j = k = 0

       
        while i < len(leftArr) and j < len(rightArr):
            if leftArr[i] < rightArr[j]:
                arr[k] = leftArr[i]
                i += 1
            else:
                arr[k] = rightArr[j]
                j += 1
            k += 1

       
        while i < len(leftArr):
            arr[k] = leftArr[i]
            i += 1
            k += 1

        while j < len(rightArr):
            arr[k] = rightArr[j]
            j += 1
            k += 1


def display(arr):
    for i in range(len(arr)):
        print(arr[i], end=" ")
    print()


if __name__ == '__main__':
    arr = [6, 5, 12, 10, 9, 1]
    
    print("Original array")
    display(arr)
    
    mergeSort(arr)

    print("Sorted array")
    display(arr)
 
Output of the program:
 Original array
 6 5 12 10 9 1 
 Sorted array
 1 5 6 9 10 12

Click here to know Quick Sort Algorithm using C , C++, Java, and Python

Merge Sort Example

Merge 2 sorted array 
Input:
	1 5 8 10 20
        4 6 9 15 40 55 92
Output:
     1 4 5 6 8 9 10 15 20 40 55 92 

JAVA Code

import java.io.*;

class Merge {
    static int[] merge(int[] arr1, int[] arr2, int n, int m){
        int ans[]=new int[n+m];
        int i=0,j=0,k=0;
        while(i<n && j<m){
            if(arr1[i]<arr2[j])
                ans[k++]=arr1[i++];
            else
                ans[k++]=arr2[j++];
        }
        
        while(i<n)
            ans[k++]=arr1[i++];
            
        while(j<m)
            ans[k++]=arr2[j++];
        
        return ans;
    }
    
    static void display(int[] arr){
        for(int i=0;i<arr.length;i++)
            System.out.print(arr[i]+" ");
    }
    
	public static void main (String[] args) {
	    int[] arr1={1,5,8,10,20};
	    int[] arr2={4,6,9,15,40,55,92};
	    
	    int[] ans = merge(arr1,arr2,arr1.length,arr2.length);
	    display(ans);
	    
	}
}

C++ Code

#include <iostream>
using namespace std;

void merge(int arr1[], int arr2[], int n, int m){
    int ans[n+m];
    int i=0,j=0,k=0;
    while(i<n && j<m){
        if(arr1[i]<arr2[j])
            ans[k++]=arr1[i++];
        else
            ans[k++]=arr2[j++];
    }
        
    while(i<n)
        ans[k++]=arr1[i++];
        
    while(j<m)
        ans[k++]=arr2[j++];
    
    for(int i=0;i<n+m;i++)
        cout<<ans[i]<<" ";
}

    
int main () {
    int arr1[]={1,5,8,10,20};
    int arr2[]={4,6,9,15,40,55,92};
    
    merge(arr1,arr2,sizeof(arr1)/sizeof(arr1[0]),sizeof(arr2)/sizeof(arr2[0]));
    return 0;
    
}

C Code

#include <stdio.h>

void merge(int arr1[], int arr2[], int n, int m){
    int ans[n+m];
    int i=0,j=0,k=0;
    while(i<n && j<m){
        if(arr1[i]<arr2[j])
            ans[k++]=arr1[i++];
        else
            ans[k++]=arr2[j++];
    }
        
    while(i<n)
        ans[k++]=arr1[i++];
        
    while(j<m)
        ans[k++]=arr2[j++];
    
    for(int i=0;i<n+m;i++)
        printf("%d ",ans[i]);
}

    
int main () {
    int arr1[]={1,5,8,10,20};
    int arr2[]={4,6,9,15,40,55,92};
    
    merge(arr1,arr2,sizeof(arr1)/sizeof(arr1[0]),sizeof(arr2)/sizeof(arr2[0]));
    return 0;
    
}

Difference between QuickSort and MergeSort

  • In terms of algorithm and complexity
    • In Quicksort, the partition of the array in the next iteration completely depends on the choice of the pivot element. We will have 2 arrays after placing the pivot to its correct position. So if we have a sorted array, the pivot will remain at the same position, leading to n^2 complexity, as no real partition will take place.
    • In Mergesort, we take the mid index which is (beg index + end index)/2. Our array will always break into two subsequent arrays with approximately equal length. This keeps the complexity to n log n and is much time-efficient
  • In terms of space complexity
    • If we are implementing our sort algorithm using recursion, then obviously our recursion stack will take n space.
    • But in merge sort in every iteration, we create two new temporary arrays. In one we copy all the left subarray and in other, we copy all the right subarray. Since all the elements are copied, it takes another n space.
    • In quicksort no such temporary array creation and copying takes place. Therefore no extra n space is needed
  • In terms of speed
    • Quicksort is faster than the merge sort because of previous explanation.
    • No temporary array, copying, etc happens in quicksort, making it much faster in execution
  • In terms of in-place
    • In-place states that the algorithm is in-place if it does not need extra memory barring some variable creation which counts to constant space.
    • Quicksort is in place but merge sort is not as it needs extra n space for creating temporary arrays whose sixes adds up to n  
  • In terms of stability
    • Stability states that the algorithm is stable if the relative ordering of the same elements in the input and output array remains the same.
    • In quicksort, a lot of swapping takes place leading it to lose its stability whereas the merge sort maintains the relative ordering, and hence it is stable.
QUICK SORTMERGE SORT
Splitting of the array depends on the value of pivot and other array elementsSplitting of array generally done on half
Worst-case time complexity is O(n2)Worst-case time complexity is O(n log n)
It takes less n space than merge sortIt takes more n space than quicksort
It works faster than other sorting algorithms for small data set like Selection sort etcIt has a consistent speed on any size of data
It is in-placeIt is out-place
Not stableStable

This brings us to the end of this article where we learned about merge sort and its implementation in various languages. Take a free course about programming by clicking the banner below

merge sort
0

LEAVE A REPLY

Please enter your comment!
Please enter your name here

one × two =