C Program for Merge Sort with Example and Explanation

A C program for merge sort uses a mergeSort function to recursively divide the array and a merge function to combine sorted parts; for example, void mergeSort(int arr[], int l, int r) divides and sorts the array between indexes l and r.

Examples

Inputarr = {5, 2, 9, 1, 5, 6}

OutputSorted array: 1 2 5 5 6 9

Inputarr = {3, 1}

OutputSorted array: 1 3

Inputarr = {10}

OutputSorted array: 10

How to Think About It

To sort an array using merge sort, first split the array into two halves until each part has one element. Then, merge these small parts back together in sorted order by comparing elements from each half. This process repeats until the whole array is sorted.

Algorithm

1

If the array has more than one element, find the middle point to divide it into two halves.

2

Recursively call merge sort on the first half.

3

Recursively call merge sort on the second half.

4

Merge the two sorted halves into one sorted array.

Code

c

#include <stdio.h>

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
    int i = 0, j = 0, k = l;
    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 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);
    }
}

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    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;
}

Output

Sorted array: 1 2 5 5 6 9 

Dry Run

Let's trace the array {5, 2, 9, 1, 5, 6} through the merge sort code.

1

Initial split

Array is split into {5, 2, 9} and {1, 5, 6}

2

Split left half

Left half {5, 2, 9} is split into {5, 2} and {9}

3

Split left-left half

{5, 2} is split into {5} and {2}

4

Merge {5} and {2}

Merge to get sorted {2, 5}

5

Merge {2, 5} and {9}

Merge to get sorted {2, 5, 9}

6

Split right half

Right half {1, 5, 6} is split into {1, 5} and {6}

7

Split right-left half

{1, 5} is split into {1} and {5}

8

Merge {1} and {5}

Merge to get sorted {1, 5}

9

Merge {1, 5} and {6}

Merge to get sorted {1, 5, 6}

10

Final merge

Merge {2, 5, 9} and {1, 5, 6} to get fully sorted {1, 2, 5, 5, 6, 9}

Step	Array State
Initial	5 2 9 1 5 6
Split halves	5 2 9 | 1 5 6
Sort left halves	2 5 9 | 1 5 6
Sort right halves	2 5 9 | 1 5 6
Final merge	1 2 5 5 6 9

Why This Works

Step 1: Divide the array

The mergeSort function splits the array into smaller parts until each part has one element, which is naturally sorted.

Step 2: Merge sorted parts

The merge function combines two sorted parts by comparing elements one by one and placing the smaller element first.

Step 3: Repeat until sorted

This splitting and merging continues recursively until the entire array is merged back into a fully sorted array.

Alternative Approaches

Iterative Merge Sort

c

#include <stdio.h>

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
    int i = 0, j = 0, k = l;
    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 mergeSortIterative(int arr[], int n) {
    for (int curr_size = 1; curr_size <= n-1; curr_size = 2*curr_size) {
        for (int left_start = 0; left_start < n-1; left_start += 2*curr_size) {
            int mid = left_start + curr_size - 1;
            int right_end = (left_start + 2*curr_size - 1 < n-1) ? left_start + 2*curr_size - 1 : n-1;
            if(mid < right_end) merge(arr, left_start, mid, right_end);
        }
    }
}

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    mergeSortIterative(arr, n);
    printf("Sorted array: ");
    for(int i=0; i<n; i++) printf("%d ", arr[i]);
    return 0;
}

This avoids recursion but is more complex to understand and write.

Using Temporary Global Array

c

#include <stdio.h>

int temp[100];

void merge(int arr[], int l, int m, int r) {
    int i = l, j = m + 1, k = l;
    while (i <= m && j <= r) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else temp[k++] = arr[j++];
    }
    while (i <= m) temp[k++] = arr[i++];
    while (j <= r) temp[k++] = arr[j++];
    for (int x = l; x <= r; x++) arr[x] = temp[x];
}

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

int main() {
    int arr[] = {5, 2, 9, 1, 5, 6};
    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;
}

Uses a global temporary array to reduce repeated memory allocation but is less flexible.

Complexity: O(n log n) time, O(n) space

Time Complexity

Merge sort divides the array into halves recursively (log n splits) and merges all elements (n) at each level, resulting in O(n log n) time.

Space Complexity

It requires extra space proportional to the array size for temporary arrays during merging, so O(n) space is used.

Which Approach is Fastest?

Recursive merge sort is easier to implement and understand, while iterative merge sort avoids recursion overhead but is more complex.

Approach	Time	Space	Best For
Recursive Merge Sort	O(n log n)	O(n)	Simplicity and clarity
Iterative Merge Sort	O(n log n)	O(n)	Avoiding recursion overhead
Global Temp Array Merge Sort	O(n log n)	O(n)	Reducing repeated memory allocation