C Merge Sort
Merge sort is one of the most important sorting algorithms you will meet in C, and it is a favorite in technical interviews because it demonstrates the divide-and-conquer strategy so cleanly. Unlike simple sorts such as bubble sort or insertion sort, merge sort guarantees O(n log n) performance no matter how the input is arranged, which makes it dependable for large or unpredictable data. Implementing it well in C means understanding recursion, how array “slices” are represented with indices, and how a temporary buffer is used to combine two sorted pieces into one. This lesson builds a complete recursive merge sort, a variant that sorts strings, and an iterative (bottom-up) version, then walks through the mistakes beginners make and how to avoid them.
Overview: How Merge Sort Works
Merge sort is a divide-and-conquer algorithm. Instead of sorting the whole array at once, it repeatedly splits the array in half until each piece contains just one element (a single element is, trivially, already sorted). Then it merges those tiny sorted pieces back together, two at a time, in the correct order, until the whole array is one sorted sequence again.
Every call to the sorting function does three things: split the current range into two halves, recursively sort the left half, recursively sort the right half, then merge the two sorted halves. The actual “sorting work” happens entirely in the merge step — the recursive calls just make sure that by the time merge() is called, both halves are already sorted.
Internally, C represents the array being sorted as one block of memory, and the algorithm never physically splits it — it just passes different left and right index boundaries into the same array. The recursion tree has a depth of about log2(n), because the array size is halved at every level, and each level does O(n) total work merging, since every element is touched once per level. Multiplying depth by work per level gives the well-known O(n log n) time complexity, and this holds for the best, average, and worst case alike — merge sort has no “bad input” that degrades it to O(n^2), unlike quicksort.
The cost of that guarantee is memory: merge() needs a temporary array to hold elements while it rearranges them, so classic merge sort uses O(n) extra space, making it not an in-place algorithm. It is, however, stable — equal elements keep their original relative order — as long as the merge step takes from the left half whenever the two elements being compared are equal.
Syntax
A recursive merge sort in C is normally written as two cooperating functions: one that sorts a range of an array, and one that merges two already-sorted halves of that range.
void merge(int arr[], int left, int mid, int right);
void mergeSort(int arr[], int left, int right);
/* mergeSort recursively splits arr[left..right] into
two halves, sorts each half, then calls merge()
to combine the two sorted halves back together */| Part | Meaning |
|---|---|
arr |
The array being sorted (passed by reference, as all C arrays are) |
left |
Index of the first element of the current range |
right |
Index of the last element of the current range (inclusive) |
mid |
Index that splits [left, right] into two halves |
mergeSort(arr, 0, n - 1) |
The typical top-level call, sorting the whole array of size n |
Examples
Example 1: Basic Recursive Merge Sort on Integers
#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 leftArr[n1], rightArr[n2];
for (i = 0; i < n1; i++)
leftArr[i] = arr[left + i];
for (j = 0; j < n2; j++)
rightArr[j] = arr[mid + 1 + j];
i = 0;
j = 0;
k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i++;
} else {
arr[k] = rightArr[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = leftArr[i];
i++;
k++;
}
while (j < n2) {
arr[k] = rightArr[j];
j++;
k++;
}
}
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(void) {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
mergeSort(arr, 0, n - 1);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}Output:
Original array: 38 27 43 3 9 82 10
Sorted array: 3 9 10 27 38 43 82 The array is split down to single elements (38 | 27 | 43 | 3 | 9 | 82 | 10), and then merge() stitches pairs back together in order at each level, until the final call merges two large sorted halves into the fully sorted array. Notice that merge() uses two variable-length arrays, leftArr and rightArr, sized exactly to the two halves it needs to combine — this is a C99 variable-length array (VLA), which is convenient here but worth being cautious with (see Common Mistakes).
Example 2: Sorting an Array of Strings
Merge sort is not limited to numbers — because the only thing it needs is a way to compare two elements, it works just as well on strings, structs, or any other data as long as you supply the right comparison.
#include <stdio.h>
#include <string.h>
void mergeStrings(char *arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
char *leftArr[n1], *rightArr[n2];
for (int i = 0; i < n1; i++)
leftArr[i] = arr[left + i];
for (int j = 0; j < n2; j++)
rightArr[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (strcmp(leftArr[i], rightArr[j]) <= 0) {
arr[k] = leftArr[i];
i++;
} else {
arr[k] = rightArr[j];
j++;
}
k++;
}
while (i < n1) { arr[k] = leftArr[i]; i++; k++; }
while (j < n2) { arr[k] = rightArr[j]; j++; k++; }
}
void mergeSortStrings(char *arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSortStrings(arr, left, mid);
mergeSortStrings(arr, mid + 1, right);
mergeStrings(arr, left, mid, right);
}
}
int main(void) {
char *words[] = {"banana", "apple", "cherry", "date", "fig"};
int n = sizeof(words) / sizeof(words[0]);
mergeSortStrings(words, 0, n - 1);
for (int i = 0; i < n; i++)
printf("%s\n", words[i]);
return 0;
}Output:
apple
banana
cherry
date
figThe structure is identical to the integer version — only the element type (char *) and the comparison (strcmp instead of <=) changed. This is the real power of merge sort: the divide-and-merge skeleton stays the same regardless of what you are sorting.
Example 3: Iterative (Bottom-Up) Merge Sort
Recursive merge sort is easy to read, but every recursive call adds a stack frame. An iterative, bottom-up version avoids recursion entirely by starting with “runs” of width 1 and doubling the run width on each pass until it covers the whole array.
#include <stdio.h>
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int leftArr[n1], rightArr[n2];
for (int i = 0; i < n1; i++) leftArr[i] = arr[left + i];
for (int j = 0; j < n2; j++) rightArr[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
arr[k++] = (leftArr[i] <= rightArr[j]) ? leftArr[i++] : rightArr[j++];
}
while (i < n1) arr[k++] = leftArr[i++];
while (j < n2) arr[k++] = rightArr[j++];
}
void iterativeMergeSort(int arr[], int n) {
for (int width = 1; width < n; width *= 2) {
for (int left = 0; left < n - width; left += 2 * width) {
int mid = left + width - 1;
int right = left + 2 * width - 1;
if (right > n - 1) right = n - 1;
merge(arr, left, mid, right);
}
}
}
int main(void) {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
iterativeMergeSort(arr, n);
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}Output:
5 6 7 11 12 13 On the first pass, width is 1, so merge() combines adjacent single elements into sorted pairs: {11,12}, {5,13}, {6,7}. On the second pass, width is 2, merging pairs into sorted runs of four: {5,11,12,13}. On the third pass, width is 4, and the final merge combines the run of four with the remaining run of two into the fully sorted array. This version uses no recursion at all, which can matter on systems with a small call stack.
How It Works Step by Step (Under the Hood)
Tracing the recursive version on a small array makes the process concrete. For arr = {6, 3, 8, 5}, calling mergeSort(arr, 0, 3) proceeds like this:
mergeSort(arr, 0, 3)computesmid = 1and callsmergeSort(arr, 0, 1)first.mergeSort(arr, 0, 1)computesmid = 0, callsmergeSort(arr, 0, 0)(a single element, returns immediately sinceleft < rightis false) andmergeSort(arr, 1, 1)(also a single element), then merges indices 0..1: {6} and {3} become {3, 6}.- Back in
mergeSort(arr, 0, 3), it now callsmergeSort(arr, 2, 3), which similarly splits into {8} and {5}, then merges them into {5, 8}. - Finally,
mergeSort(arr, 0, 3)callsmerge(arr, 0, 1, 3), combining the two now-sorted halves {3, 6} and {5, 8} by comparing their fronts: 3 < 5 so 3 is placed first, then 5 < 6 so 5 is placed next, then 6 < 8 so 6 is placed, then 8 is placed last, giving {3, 5, 6, 8}.
Notice that the recursion always goes “all the way down” on the left branch before touching the right branch, and that every merge() call only ever combines two ranges that are already individually sorted — that invariant is what makes the algorithm correct. Each call frame on the stack only needs to remember left, mid, and right, which is why the stack usage stays small (proportional to log2(n)) even though the total amount of merging work is proportional to n log n.
Common Mistakes
Mistake 1: Passing the wrong bounds to the recursive calls. A very common typo is calling the right-hand recursion with mid instead of mid + 1:
/* Wrong: reuses mid as the left half's right edge instead of
moving the right half's left edge past it */
mergeSort(arr, left, mid);
mergeSort(arr, mid, right); /* should be mid + 1 */This causes the element at index mid to be included in both halves, and on some inputs it can lead to infinite recursion because the range never shrinks. The fix is to always give the right half a starting index of mid + 1:
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);Mistake 2: Computing mid as (left + right) / 2. For huge arrays where left + right could exceed INT_MAX, this addition overflows before the division happens, producing a negative or garbage index. The safer form avoids adding two large indices directly:
int mid = left + (right - left) / 2;For everyday array sizes this rarely bites, but it is a habit worth building since the safe version costs nothing.
Mistake 3: Allocating a huge VLA on the stack. The examples above declare int leftArr[n1], rightArr[n2]; as variable-length arrays. This is convenient, but VLAs live on the call stack, and sorting a very large array (say, tens of millions of elements) can exhaust the stack and crash the program with no warning from the compiler. For large or untrusted input sizes, allocate the temporary buffers with malloc() (once, outside the recursion, sized to n) instead of re-declaring VLAs on every call, and remember to free() them.
Mistake 4: Forgetting the leftover elements after the main merge loop. The while (i < n1 && j < n2) loop stops as soon as either half is exhausted, but one half almost always still has elements left over. Skipping the two follow-up while loops that copy the remainder silently drops elements from the sorted result — the array will be shorter than expected. Always keep both cleanup loops after the main comparison loop.
Best Practices
- Use
left + (right - left) / 2rather than(left + right) / 2to compute the midpoint, to avoid integer overflow on large ranges. - For very large arrays, allocate one reusable temporary buffer with
malloc()up front instead of declaring new VLAs in every recursive call, and always pair it withfree(). - Use
<=(not<) when comparing equal elements inmerge(), so that elements from the left half are placed first — this keeps the sort stable. - For small subarrays (roughly 10-20 elements or fewer), switch to insertion sort inside the recursion; insertion sort has less overhead at that scale and many production merge sorts use this hybrid approach.
- Prefer the iterative (bottom-up) version in environments with a limited call stack, such as embedded systems, since it needs no recursion.
- Double-check index bounds with a debugger or printf traces on a small (4-6 element) array before trusting the implementation on real data.
Practice Exercises
- Exercise 1: Modify the
merge()function from Example 1 so thatmergeSort()sorts the array in descending order instead of ascending order. Only one comparison operator needs to change. - Exercise 2: Write a function that counts the number of inversions in an array (pairs of elements that are out of order relative to each other) by modifying
merge()to increment a counter whenever an element is taken from the right half while elements remain in the left half. For the array{2, 4, 1, 3, 5}, your function should report 3 inversions. - Exercise 3: Merge sort does not require random access to work, only sequential access to two already-sorted sequences. Sketch (in comments or pseudocode) how you would adapt the algorithm to sort a singly linked list instead of an array, without needing a separate temporary array for the merge step.
Summary
- Merge sort is a divide-and-conquer algorithm: split the array in half recursively, then merge sorted halves back together.
- It guarantees O(n log n) time in the best, average, and worst case, unlike quicksort’s worst-case O(n^2).
- It uses O(n) extra memory for temporary buffers during merging, so it is not in-place.
- It is stable when the merge step takes from the left half on ties, preserving the original order of equal elements.
- The same split-and-merge skeleton works for any data type as long as you supply a comparison, as shown with the string example.
- An iterative, bottom-up version achieves the same result without recursion, which is useful when stack space is limited.
- Common bugs include off-by-one errors in the recursive bounds, integer overflow when computing the midpoint, oversized VLAs on the stack, and forgetting to copy leftover elements after the main merge loop.
