Merge Sort is a powerful, stable sorting algorithm that also follows the Divide and Conquer strategy. Unlike Quick Sort, which splits based on a pivot value, Merge Sort splits the array based on position—cutting the list perfectly in half every time until individual elements remain. It then "merges" these small sorted lists back together into larger sorted lists.

Imagine you have a shuffled deck of cards. You cut the deck in half, then cut those halves in half, and keep going until you have 52 individual cards spread out on the table. Since a single card is technically "sorted" (it has no other card to be out of order with), you then start picking up two cards at a time, arranging them in order, and building a small pile. You then merge two small piles into a medium pile, maintaining the order. Eventually, you merge the two final half-decks into one perfectly sorted deck.

The magic of this algorithm happens in the "Merge" phase, not the "Divide" phase.

• Divide: Find the middle index m and recursively call the sort function for the left half and right half.
• Conquer: Once the sub-arrays are sorted, combine them.
• The Merge Helper: We compare the "front" of both sub-arrays. Whichever element is smaller gets placed into our final array first. We repeat this until one sub-array is empty, then dump the remaining elements of the other sub-array into the final list.

Let's trace the algorithm on a small array.

Below is the implementation of Merge Sort in multiple programming languages. The merge function is the heart of the algorithm, efficiently combining two sorted sub-arrays into one.

#include <stdio.h>
#include <stdlib.h>
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    int* L = (int*)malloc(n1 * sizeof(int));
    int* R = (int*)malloc(n2 * sizeof(int));
    
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
    
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j])
            arr[k++] = L[i++];
        else
            arr[k++] = R[j++];
    }
    
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
    
    free(L);
    free(R);
}
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}
int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    mergeSort(arr, 0, n - 1);
    
    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

Merge Sort is famous for its predictable performance. Unlike Quick Sort, it does not have a "bad" worst-case time scenario.

Time Complexity

Space Complexity

While Quick Sort is faster for generic arrays, Merge Sort is the king of specific domains.