Merge sort in C is a classic divide-and-conquer sorting algorithm that guarantees O(n log n) time in all cases. It splits an array into halves, recursively sorts each half, then merges the sorted halves back together. Unlike bubble sort or insertion sort, merge sort never degrades to O(n²) — making it the preferred choice when worst-case performance matters.
This page covers the complete C implementation with a step-by-step trace, time and space analysis, and comparison against other sorting algorithms.
How Merge Sort Works — Step by Step
The algorithm has two phases:
- Divide: Split the array into two halves. Recursively split each half until you have single-element subarrays (a single element is always sorted).
- Merge: Merge pairs of sorted subarrays back together, comparing front elements 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:
[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(void)
{
int n, i;
int *arr;
printf("Enter number of elements: ");
scanf("%d", &n);
arr = (int *)malloc(n * sizeof(int));
if (!arr) { fprintf(stderr, "malloc failed\n"); return 1; }
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");
free(arr);
return 0;
}
How to Compile and Run
gcc -Wall -o mergesort mergesort.c
./mergesort
Sample Input and Output
Enter number of elements: 7 Enter 7 elements: 38 27 43 3 9 82 10 Before sorting: 38 27 43 3 9 82 10 After merge sort: 3 9 10 27 38 43 82
Code Explanation
merge_sort(arr, left, right): The recursive divide step.mid = left + (right - left) / 2avoids integer overflow that would occur with(left + right) / 2on large indices. Recurses on each half, then merges.merge(arr, left, mid, right): Creates temporary arraysL[]andR[]for each half, then merges them back intoarr[]in sorted order by comparing front elements.- Leftover loop: After one half empties, the remaining elements in the other are already in order and copied directly.
malloc/free: The input array and temp arrays all use heap allocation — safe for any n, unlike VLAs which can overflow the stack for large inputs.
Time and Space Complexity
| Case | Time | Space |
|---|---|---|
| Best | O(n log n) | O(n) |
| Average | O(n log n) | O(n) |
| Worst | O(n log n) | O(n) |
The log n depth comes from the recursion tree — you can halve an array log₂ n times. At each of those levels, the merge step does O(n) work in total across all calls. Hence O(n log n) overall.
The O(n) space is the cost of the temporary arrays in the merge step. This is the main trade-off against heap sort and quick sort, which sort in-place.
Merge Sort vs Other Sorting Algorithms
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
When to choose merge sort:
- You need a stable sort (equal elements keep their original relative order)
- You’re sorting a linked list — merge sort is optimal here since it doesn’t need random index access
- You need guaranteed O(n log n) — quick sort degrades to O(n²) on sorted or nearly-sorted input with naive pivot selection
- External sorting — data too large for RAM; files are split into sorted chunks and merged
What This Program Teaches
- The divide-and-conquer pattern: split into independent subproblems, solve each, combine the results
- Why
mid = left + (right - left) / 2is safer than(left + right) / 2— the latter overflows when both indices are large - Stable sorting: the
L[i] <= R[j]condition (not<) is what makes merge sort stable — equal elements from the left half are placed first - The cost of guaranteed worst-case performance: O(n) auxiliary space vs O(1) for heap sort
Related Programs
- Quick Sort in C
- Insertion Sort in C
- Heap Sort in C
- Bubble Sort in C
- Selection Sort in C
- C Aptitude Questions — Sorting and Algorithms
As an Amazon Associate we earn from qualifying purchases.
Recommended Book
Sorting algorithms and recursion are covered in depth in The C Programming Language by Kernighan & Ritchie — the book that defined modern C. Also on Amazon.com.