Merge Sort in C – Step-by-Step Program with Explanation

Sorting algorithms are an essential part of data structures. Among them, merge sort is one of the most efficient and stable sorting techniques, based on the divide-and-conquer approach. In this post, you’ll learn how to implement merge sort in C, with a clear explanation and code.

---

What is Merge Sort?

Merge sort divides the input array into two halves, recursively sorts them, and then merges the sorted halves to produce the final sorted array. It ensures a time complexity of O(n log n) in all cases (worst, best, average).

---

Merge Sort Algorithm Steps:

1. Divide the array into two halves.
2. Recursively sort both halves.
3. Merge the two sorted halves into one.

---

Merge Sort in C – Full Program:

#include <stdio.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[n1], R[n2];

    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++];
}

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);
    }
}

void printArray(int arr[], int size) {
    for (int 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:\n");
    printArray(arr, size);

    mergeSort(arr, 0, size - 1);

    printf("Sorted array using Merge Sort:\n");
    printArray(arr, size);

    return 0;
}

---

Why Use Merge Sort?

• Consistent O(n log n) performance
• Stable sorting algorithm
• Ideal for linked lists and large datasets

This merge sort in C program is great for academic use, DSA practice, or job interviews.