Implement Merge Sort in C
Goal: Implement merge sort from scratch in C. Understand the divide-and-conquer strategy, verify O(n log n) behavior, and compare with stdlib’s qsort.
Prerequisites: Sorting Algorithms, Recursion, Big O Notation, C Language Essentials
The Idea
Split the array in half, recursively sort each half, then merge the two sorted halves. The merge step does the real work — it combines two sorted arrays into one sorted array in O(n).
[38, 27, 43, 3, 9, 82, 10]
/ \
[38, 27, 43, 3] [9, 82, 10]
/ \ / \
[38, 27] [43, 3] [9, 82] [10]
/ \ / \ / \ |
[38][27] [43][3] [9][82] [10]
\ / \ / \ / |
[27, 38] [3, 43] [9, 82] [10]
\ / \ /
[3, 27, 38, 43] [9, 10, 82]
\ /
[3, 9, 10, 27, 38, 43, 82]
Step 1: The Merge Function
This is the core. Given two sorted subarrays, produce one sorted array.
#include <stdlib.h>
#include <string.h>
// Merge arr[left..mid] and arr[mid+1..right] into arr[left..right]
void merge(int *arr, int *tmp, int left, int mid, int right) {
// Copy both halves into tmp
memcpy(tmp + left, arr + left, (right - left + 1) * sizeof(int));
int i = left; // pointer into left half
int j = mid + 1; // pointer into right half
int k = left; // write pointer into arr
while (i <= mid && j <= right) {
if (tmp[i] <= tmp[j]) // <= makes it stable
arr[k++] = tmp[i++];
else
arr[k++] = tmp[j++];
}
// Copy remaining elements (only left half needs this — right is already in place)
while (i <= mid)
arr[k++] = tmp[i++];
}Why a temporary buffer
Merging in-place is possible but complex and slow. Allocating a temp buffer once and reusing it keeps the implementation simple and the constant factor low.
Step 2: The Recursive Sort
static void merge_sort_recursive(int *arr, int *tmp, int left, int right) {
if (left >= right)
return; // base case: 0 or 1 elements
int mid = left + (right - left) / 2; // avoids integer overflow
merge_sort_recursive(arr, tmp, left, mid);
merge_sort_recursive(arr, tmp, mid + 1, right);
merge(arr, tmp, left, mid, right);
}
void merge_sort(int *arr, int n) {
int *tmp = malloc(n * sizeof(int));
merge_sort_recursive(arr, tmp, 0, n - 1);
free(tmp);
}Key insight: mid = left + (right - left) / 2 instead of (left + right) / 2 prevents integer overflow when left and right are large.
Step 3: Test It
#include <stdio.h>
#include <assert.h>
void print_array(int *arr, int n) {
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
int is_sorted(int *arr, int n) {
for (int i = 1; i < n; i++)
if (arr[i] < arr[i - 1]) return 0;
return 1;
}
int main(void) {
// Basic test
int a[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(a) / sizeof(a[0]);
printf("Before: "); print_array(a, n);
merge_sort(a, n);
printf("After: "); print_array(a, n);
assert(is_sorted(a, n));
// Edge cases
int empty[] = {};
merge_sort(empty, 0); // should not crash
int single[] = {42};
merge_sort(single, 1);
assert(single[0] == 42);
int already_sorted[] = {1, 2, 3, 4, 5};
merge_sort(already_sorted, 5);
assert(is_sorted(already_sorted, 5));
int reversed[] = {5, 4, 3, 2, 1};
merge_sort(reversed, 5);
assert(is_sorted(reversed, 5));
int duplicates[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
merge_sort(duplicates, 11);
assert(is_sorted(duplicates, 11));
// Random large test
int big[10000];
for (int i = 0; i < 10000; i++)
big[i] = rand() % 100000;
merge_sort(big, 10000);
assert(is_sorted(big, 10000));
printf("All tests passed!\n");
return 0;
}gcc -Wall -Wextra -g -o mergesort mergesort.c
./mergesort
# Before: 38 27 43 3 9 82 10
# After: 3 9 10 27 38 43 82
# All tests passed!
valgrind --leak-check=full ./mergesortStep 4: Compare with qsort
#include <time.h>
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
void benchmark(int n) {
int *a = malloc(n * sizeof(int));
int *b = malloc(n * sizeof(int));
for (int i = 0; i < n; i++)
a[i] = b[i] = rand();
clock_t start = clock();
merge_sort(a, n);
double ms_merge = (double)(clock() - start) / CLOCKS_PER_SEC * 1000;
start = clock();
qsort(b, n, sizeof(int), compare);
double ms_qsort = (double)(clock() - start) / CLOCKS_PER_SEC * 1000;
printf("n=%d: merge_sort=%.1fms, qsort=%.1fms\n", n, ms_merge, ms_qsort);
free(a); free(b);
}
// In main:
benchmark(10000);
benchmark(100000);
benchmark(1000000);qsort (typically introsort) is usually faster due to lower constant factors and cache-friendliness. But merge sort is stable and always O(n log n) — quicksort’s worst case is O(n²).
Complexity Analysis
| 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 recursion tree has log₂(n) levels. Each level does O(n) work in the merge step. Total: O(n log n). The O(n) space is for the temporary buffer.
Level 0: merge 1 array of n → n comparisons
Level 1: merge 2 arrays of n/2 → n comparisons
Level 2: merge 4 arrays of n/4 → n comparisons
...
Level log₂(n): merge n arrays of 1 → n comparisons
Total: n × log₂(n)
Exercises
-
Bottom-up merge sort: Implement merge sort iteratively. Start with subarrays of size 1, merge pairs into size 2, then size 4, etc. No recursion needed.
-
Generic sort: Modify
merge_sortto sort any type by accepting a comparator function pointer (same signature asqsort). Sort an array of strings. -
Inversion count: Modify merge sort to count the number of inversions (pairs where i < j but a[i] > a[j]). The merge step can count inversions in O(n). This is a classic divide and conquer application.
-
Natural merge sort: Detect already-sorted runs in the input and merge those directly instead of splitting to individual elements. This makes it faster on partially sorted data (like Python’s Timsort).
Next: 03 - Debug a Segfault with GDB — learn to diagnose crashes instead of guessing.