Merge sort is the sorting algorithm that follows the divide and conquer technique. It is a popular and efficient sorting algorithm.

It splits the given list into two equal lists i.e. sub-list. calls itself for the two lists and then merges the two sorted lists.

The process of splitting and merging can be carried out recursively till there is only one element in the list.

An array with a single element is always sorted.

 

Time Complexity

Case	Time Complexity
Best Case	O(n log n)
Average Case	O(n log n)
Worst Case	O(n log n)

 

Best Case O(n log n): It occurs when there is no sorting needed, i.e. the array is already sorted.

Average Case O(n log n): The array elements are in a jumbled order that is not properly ascending and descending.

Worst Case O(n log n): This occurs when the array elements need to be sorted in reverse order.

 

Space Complexity

Space Complexity	O(n)
Stable	Yes

 

A merge sort required extra variables for swapping. Hence, the space complexity of merge sorting is O(n).

 

Example

C Program

#include <stdio.h>  
  
/* Function to merge the subarrays of a[] */  
void merge(int a[], int beg, int mid, int end) {    
    int i, j, k;  
    int n1 = mid - beg + 1;    
    int n2 = end - mid;    
    
    //temporary arrays  
    int leftArray[n1], rightArray[n2]; 
      
    /* copy data to temp arrays */  
    for (int i = 0; i < n1; i++)    
        leftArray[i] = a[beg + i];    
    for (int j = 0; j < n2; j++)    
        rightArray[j] = a[mid + 1 + j];    
      
    i = 0;      /* initial index of first sub-array */  
    j = 0;      /* initial index of second sub-array */   
    k = beg;    /* initial index of merged sub-array */  
      
    while (i < n1 && j < n2) {    
        if(leftArray[i] <= rightArray[j]) {    
            a[k] = leftArray[i];    
            i++;    
        } else {    
            a[k] = rightArray[j];    
            j++;    
        }    
        k++;    
    }    
    while (i < n1) {    
        a[k] = leftArray[i];    
        i++;    
        k++;    
    }    
      
    while (j < n2) {    
        a[k] = rightArray[j];    
        j++;    
        k++;    
    }    
}    
  
void mergeSort(int a[], int beg, int end) {  
    if (beg < end) {  
        int mid = (beg + end) / 2;  
        mergeSort(a, beg, mid);  
        mergeSort(a, mid + 1, end);  
        merge(a, beg, mid, end);  
    }  
}  
  
/* Function to print the array */  
void print(int a[], int n) {  
    for (int i = 0; i < n; i++)  
        printf("%d ", a[i]);  
    printf("n");  
}  
  
int main() {  
    int a[] = { 50, 20, 32, 13, 30, 18, 17, 40, 42 };  
    int n = sizeof(a) / sizeof(a[0]);  
    printf("Before sorting array elements are - n");  
    print(a, n);  
    mergeSort(a, 0, n - 1);  
    printf("After sorting array elements are - n");  
    print(a, n);  
    return 0;  
}

 

Java Program

class MergeSort {  
  
    /* Function to merge the subarrays of a[] */  
    static void merge(int a[], int beg, int mid, int end) {    
        int i, j, k;  
        int n1 = mid - beg + 1;    
        int n2 = end - mid;    
          
        /* temporary Arrays */  
        int leftArray[] = new int[n1];  
        int rightArray[] = new int[n2];  
          
        /* copy data to temp arrays */  
        for (i = 0; i < n1; i++)    
            leftArray[i] = a[beg + i];    
        for (j = 0; j < n2; j++)    
            rightArray[j] = a[mid + 1 + j];    
          
        i = 0; /* initial index of first sub-array */  
        j = 0; /* initial index of second sub-array */   
        k = beg;  /* initial index of merged sub-array */  
          
        while (i < n1 && j < n2) {    
            if(leftArray[i] <= rightArray[j])  {    
                a[k] = leftArray[i];    
                i++;    
            } else {    
                a[k] = rightArray[j];    
                j++;    
            }    
            k++;    
        }    
        while (i < n1) {    
            a[k] = leftArray[i];    
            i++;    
            k++;    
        }    
          
        while (j < n2) {    
            a[k] = rightArray[j];    
            j++;    
            k++;    
        }    
    }    
  
    static void mergeSort(int a[], int beg, int end) {  
        if (beg < end) {  
            int mid = (beg + end) / 2;  
            mergeSort(a, beg, mid);  
            mergeSort(a, mid + 1, end);  
            merge(a, beg, mid, end);  
        }  
    }  
      
    /* Function to print the array */  
    static void print(int a[], int n) {  
        for (int i = 0; i < n; i++)  
            System.out.print(a[i] + " ");  
    }  
      
    public static void main(String args[]) {  
        int a[] = { 50, 20, 32, 13, 30, 18, 17, 40, 42 };   
        int n = a.length;  
        System.out.println("nBefore sorting array elements are - ");  
        print(a, n);  
        mergeSort(a, 0, n - 1);  
        System.out.println("nAfter sorting array elements are - ");  
        print(a, n);  
        System.out.println("");  
    }  
}