Merge sort is a classic divide and conquer sorting algorithm. It splits an array in half, recursively sorts each half, then merges the two sorted halves back together. Unlike bubble sort or insertion sort, merge sort guarantees O(n log n) performance in all cases — best, average, and worst.

It is the algorithm of choice when stable sorting is required or when sorting linked lists, and it forms the basis of many standard library sort implementations.

How Merge Sort Works — Step by Step

The algorithm has two phases:

1. Divide: Split the array into two halves. Recursively split each half until you have single-element arrays (a single element is always sorted).
2. Conquer (Merge): Merge pairs of sorted subarrays back together, comparing elements one by one and placing the smaller one first.

Example: Sorting [38, 27, 43, 3, 9, 82, 10]

Divide phase:
[38, 27, 43, 3, 9, 82, 10]
     /                \
[38, 27, 43]        [3, 9, 82, 10]
   /     \            /          \
[38]  [27, 43]    [3, 9]      [82, 10]
       /    \      /   \       /    \
     [27]  [43]  [3]   [9]  [82]  [10]

Merge phase (building back up):
[27, 43]  →  merge [27] and [43]
[3, 9]    →  merge [3] and [9]
[10, 82]  →  merge [10] and [82]
[27, 38, 43]  →  merge [38] and [27, 43]
[3, 9, 10, 82]  →  merge [3, 9] and [10, 82]
[3, 9, 10, 27, 38, 43, 82]  →  final merge

C Program for Merge Sort

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

void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int *L = (int *)malloc(n1 * sizeof(int));
    int *R = (int *)malloc(n2 * sizeof(int));

    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    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 merge_sort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

int main() {
    int n, i;

    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n];
    printf("Enter %d elements:\n", n);
    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    printf("Before sorting: ");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);

    merge_sort(arr, 0, n - 1);

    printf("\nAfter merge sort: ");
    for (i = 0; i < n; i++)
        printf("%d ", arr[i]);

    printf("\n");
    return 0;
}

Code Explanation

• merge_sort(arr, left, right): The recursive divide step. Calculates mid = left + (right - left) / 2 (this form avoids integer overflow vs (left+right)/2), then recurses on each half before merging.
• merge(arr, left, mid, right): The conquer step. Creates two temporary arrays L[] and R[] holding copies of each half, then merges them back into arr[] in sorted order by comparing the front elements of each temp array.
• Leftover elements: After one half is exhausted, the remaining elements in the other half are already sorted and copied directly — the two while loops at the end handle this.
• malloc / free: Dynamic memory is used so the function works for any subarray size, not just a fixed maximum.

Sample Input and Output

Enter number of elements: 6
Enter 6 elements:
64 34 25 12 22 11

Before sorting: 64 34 25 12 22 11
After merge sort: 11 12 22 25 34 64

Time and Space Complexity

Merge sort is one of the few sorting algorithms with guaranteed O(n log n) in all cases. The space complexity is O(n) because the merge step needs temporary arrays to hold the two halves. This makes merge sort less suitable for memory-constrained environments compared to in-place sorts like heap sort or quick sort.

The log n factor comes from the number of times you can halve the array (depth of the recursion tree). At each level, you do O(n) work for the merging, giving O(n log n) total.

Merge Sort vs Other Sorting Algorithms

When to use merge sort: when you need a stable sort, when sorting linked lists (merge sort is optimal for linked lists since it doesn’t require random access), or when you need guaranteed worst-case performance.

Applications of Merge Sort

• External sorting: Sorting data too large to fit in memory — files are split into chunks, each sorted, then merged. Hard disk sorting uses this approach.
• Sorting linked lists: Merge sort is preferred over quick sort for linked lists since it does not require random index access.
• Counting inversions: The merge step can count how many elements are out of order — useful in recommendation systems and order statistics.
• Standard libraries: Java’s Arrays.sort() for objects and Python’s sort() (Timsort) are based on merge sort.

Related Programs

• C Program to Implement Quick Sort
• C Program to Implement Insertion Sort
• C Program to Implement Heap Sort
• C Program to Implement Bubble Sort
• C Program to Implement Selection Sort

As an Amazon Associate we earn from qualifying purchases.

Further Reading

The definitive reference for C — The C Programming Language by Brian Kernighan and Dennis Ritchie. Covers every concept on this site: pointers, arrays, structs, file I/O, and the standard library. Worth having on your desk.