Merge Sort

It is also a Divide and Conquer algorithm like Quick Sort.

Conceptually, a merge sort works as follows:

1. Divide the unsorted list into n sub lists, each containing one element as a list of one element is considered sorted.

2. Repeatedly merge sub lists to produce new sorted sub lists until there is only one sub list remaining. This will be the sorted list.

---

Animated Example:

An example of merge sort. First divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally all the elements are sorted and merged.

---

Implementation using C:

#include<stdlib.h> 
#include<stdio.h> 
  
// Merges two subarrays of arr[]. 

void merge(int arr[], int l, int m, int r) 
{ 
    int i, j, k; 
    int p = m - l + 1; 
    int q =  r - m; 
  
    /* create temp arrays */
    int L[p], R[q]; 
  
    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < p; i++) 
        L[i] = arr[l + i]; 
    for (j = 0; j < q; j++) 
        R[j] = arr[m + 1+ j]; 
  
    /* Merge the temp arrays back into arr[l..r]*/
    i = 0; // Initial index of first subarray 
    j = 0; // Initial index of second subarray 
    k = l; // Initial index of merged subarray 
    while (i < p && j < q) 
    { 
        if (L[i] <= R[j]) 
        { 
            arr[k] = L[i]; 
            i++; 
        } 
        else
        { 
            arr[k] = R[j]; 
            j++; 
        } 
        k++; 
    } 
  
    /* Copy the remaining elements of L[], if there 
       are any */
    while (i < p) 
    { 
        arr[k] = L[i]; 
        i++; 
        k++; 
    } 
  
    /* Copy the remaining elements of R[], if there 
       are any */
    while (j < q) 
    { 
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
} 
  
/* l is for left index and r is right index of the 
   sub-array of arr to be sorted */
void merge_Sort(int arr[], int l, int r) 
{ 
    if (l < r) 
    { 
        // Same as (l+r)/2, but avoids overflow for 
        // large l and h 
        int m = l+(r-l)/2; 
  
        // Sort first and second halves 
        merge_Sort(arr, l, m); 
        merge_Sort(arr, m+1, r); 
  
        merge(arr, l, m, r); 
    } 
} 
  
void print_Array(int A[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
        printf("%d ", A[i]); 
    printf("\n"); 
} 
  

int main() 
{ 
    int arr[] = {12, 11, 13, 5, 6, 7}; 
    int arr_size = sizeof(arr)/sizeof(arr[0]); 
  
    printf("Given array is \n"); 
    print_Array(arr, arr_size); 
  
    merge_Sort(arr, 0, arr_size - 1); 
  
    printf("\n Sorted array is \n"); 
    print_Array(arr, arr_size); 
    return 0; 
} 

---

Miscellaneous:

Auxiliary Space: O(n)

Algorithmic Paradigm: Divide and Conquer

Sorting In Place: No in a typical implementation

Stable: Yes

For Time complexity click here.