Merge Sort Sorting Algorithm

Merge Sort is one of the most efficient sorting algorithms which follows the divide and conquer approach. It is based on the idea of dividing an array into smaller subarrays, sorting them, and then merging them back together. Merge sort is a stable sorting algorithm which means that it maintains the relative order of equal elements in the sorted output.

How Merge Sort Works

Merge Sort works by dividing the array into two halves recursively until each subarray has only one element. Then, it merges the subarrays together in a sorted manner using a merge function.

Step by Step Algorithm of Merge Sort

The steps involved in the Merge Sort Algorithm are as follows:

Divide the array into two halves.

Recursively sort the left half.

Recursively sort the right half.

Merge the sorted left and right halves using a merge function.

Example Of Merge Sort

Divide the unsorted array into two subarrays of approximately equal size.

6 5 3 1 | 8 7 2 4

Recursively divide each subarray.

6 5 | 3 1 | 8 7 | 2 4

6 |5 | 3 |1 | 8 |7 | 2 |4

Merge the two sorted subarrays to produce a single sorted subarray.

6 |5 | 3 |1 | 8 |7 | 2 |4

5 6 | 1 3 | 7 8 | 2 4

1 3 5 6 | 2 4 7 8

1 2 3 4 5 6 7 8

Merge Sort Implementation in C

#include <stdio.h>
#include <stdlib.h>

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
    
    int L[n1], R[n2];
    
    for(i = 0; i < n1; i++) {
        L[i] = arr[l + i];
    }
    
    for(j = 0; j < n2; j++) {
        R[j] = arr[m + 1 + j];
    }
    
    i = 0;
    j = 0;
    k = l;
    
    while(i < n1 && j < n2) {
        if(L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    
    while(i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    
    while(j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r) {
    if(l < r) {
        int m = l + (r - l) / 2;
        
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        
        merge(arr, l, m, r);
    }
}

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

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf("Original array: ");
    printArray(arr, size);
    
    mergeSort(arr, 0, size - 1);
    
    printf("Sorted array: ");
    printArray(arr, size);
    
    return 0;
}

Output

Original array: 38 27 43 3 9 82 10 
Sorted array: 3 9 10 27 38 43 82

Time and Space Complexity of Merge Sort

Best Case: The best case time complexity of Merge Sort is O(nlogn). This occurs when the input array is already sorted, and the merge function can simply combine the two halves without any comparisons.

Average Case: The average case time complexity of Merge Sort is also O(nlogn). This occurs when the input array is randomly ordered, and the divide and conquer approach is utilized to sort the array.

Worst Case: The worst case time complexity of Merge Sort is O(nlogn). This occurs when the input array is in reverse order, and each subarray has to be divided into its individual elements before being merged.

The space complexity of Merge Sort is O(n) since it requires additional memory for the merge function.

Advantages and Disadvantages of Merge Sort

Advantages of Merge Sort

Merge Sort is a stable sorting algorithm which means it preserves the relative order of equal elements in the input array.

Merge Sort is an efficient algorithm with a time complexity of O(nlogn) in the average and worst case scenarios.

Merge Sort is a parallelizable algorithm which means that it can be run on multiple processors for faster sorting.

Disadvantages of Merge Sort

Merge Sort has a space complexity of O(n) which can be a limitation for large arrays.

Merge Sort requires an additional merge function which can increase the complexity of the code.