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 three complete, tested implementations — the standard recursive version, the bottom-up iterative version, and merge sort for linked lists — plus a step-by-step trace of the merge itself, complexity analysis, common mistakes, and answers to the questions interviewers actually ask.
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
The Merge Step in Detail
The merge is where all the real work happens, and it’s the part beginners get wrong. Watch the final merge of L = [27, 38, 43] and R = [3, 9, 10, 82]. Two read pointers i and j walk the two halves; a write pointer k fills the output. At each step, whichever front element is smaller gets copied:
Step L[i] R[j] smaller output so far 1 27 3 3 [3] 2 27 9 9 [3, 9] 3 27 10 10 [3, 9, 10] 4 27 82 27 [3, 9, 10, 27] 5 38 82 38 [3, 9, 10, 27, 38] 6 43 82 43 [3, 9, 10, 27, 38, 43] 7 — 82 82 [3, 9, 10, 27, 38, 43, 82] ← leftover copied
Each element is looked at once, so merging two halves of total length n costs O(n) comparisons and copies. Note step 7: when one half runs out, the rest of the other half is already sorted and is copied straight across — that’s what the two “leftover” loops in the code below do.
C Program for Merge Sort (Recursive)
#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 — exactly the pointer walk traced above.- Leftover loops: 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.
Bottom-Up Merge Sort (Iterative, No Recursion)
The recursive version is the one textbooks teach, but merge sort doesn’t need recursion at all. The bottom-up version starts from runs of width 1 (single elements — already sorted) and merges adjacent runs of width 1, then 2, then 4, and so on until one run covers the whole array. Same O(n log n) time, no recursion depth to worry about, and a single reusable temp buffer instead of one allocation per merge:
#include <stdio.h>
#include <stdlib.h>
void merge(int arr[], int temp[], int left, int mid, int right)
{
int i = left, j = mid + 1, k = left;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
for (i = left; i <= right; i++)
arr[i] = temp[i];
}
void merge_sort_iterative(int arr[], int n)
{
int width, left;
int *temp = (int *)malloc(n * sizeof(int));
if (!temp) { fprintf(stderr, "malloc failed\n"); exit(1); }
/* width doubles each pass: merge runs of 1, then 2, then 4 ... */
for (width = 1; width < n; width *= 2) {
for (left = 0; left < n - width; left += 2 * width) {
int mid = left + width - 1;
int right = (left + 2 * width - 1 < n - 1)
? left + 2 * width - 1
: n - 1;
merge(arr, temp, left, mid, right);
}
}
free(temp);
}
int main(void)
{
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);
int i;
merge_sort_iterative(arr, n);
printf("Sorted: ");
for (i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
return 0;
}
The pass structure for our 7-element array: widths 1, 2, 4 — three passes, matching the log₂ 7 ≈ 2.8 levels of the recursion tree. The bottom-up form is also the basis of external sorting, where sorted chunks on disk are merged pass by pass.
Merge Sort for Linked Lists
Merge sort is the sorting algorithm for linked lists. Quick sort and heap sort rely on O(1) random access by index, which lists don’t have — but merging two sorted lists only needs sequential access and pointer relinking, so it costs no extra memory at all. The list is split with the classic slow/fast pointer technique:
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
/* Split the list into two halves using slow/fast pointers.
Returns the head of the second half. */
struct node *split(struct node *head)
{
struct node *slow = head, *fast = head->next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next; /* head of second half */
slow->next = NULL; /* cut the list */
return fast;
}
struct node *merge_lists(struct node *a, struct node *b)
{
struct node dummy;
struct node *tail = &dummy;
dummy.next = NULL;
while (a && b) {
if (a->data <= b->data) {
tail->next = a;
a = a->next;
} else {
tail->next = b;
b = b->next;
}
tail = tail->next;
}
tail->next = a ? a : b;
return dummy.next;
}
struct node *merge_sort_list(struct node *head)
{
struct node *second;
if (!head || !head->next)
return head; /* 0 or 1 node: already sorted */
second = split(head);
head = merge_sort_list(head);
second = merge_sort_list(second);
return merge_lists(head, second);
}
Three things to notice:
- No element copying.
merge_listsrearrangesnextpointers — nodes never move in memory. That’s why linked-list merge sort is O(1) auxiliary space (plus O(log n) recursion stack). - The dummy node trick. A stack-allocated
dummyhead means no special case for “which node starts the merged list” — the answer is alwaysdummy.next. - Slow/fast splitting. When
fastreaches the end,slowis at the midpoint. Startingfastathead->next(nothead) makes the split land correctly for even-length lists.
This is exactly the pattern behind sorting a linked list and appears constantly in interviews — it combines pointer manipulation and recursion in one question.
Time and Space Complexity
| Variant | Best | Average | Worst | Extra space |
|---|---|---|---|---|
| Recursive (array) | O(n log n) | O(n log n) | O(n log n) | O(n) + O(log n) stack |
| Bottom-up (array) | O(n log n) | O(n log n) | O(n log n) | O(n), no recursion |
| Linked list | O(n log n) | O(n log n) | O(n log n) | O(log n) stack only |
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 for arrays is the cost of the temporary buffer in the merge step. This is the main trade-off against heap sort and quick sort, which sort in-place. For linked lists the trade-off disappears — merging is pointer relinking, not copying.
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
Common Mistakes to Avoid
- Recursing on
midin both halves. The calls must bemerge_sort(arr, left, mid)andmerge_sort(arr, mid + 1, right). Passingmidto both (ormid - 1/mid) either drops an element or recurses forever on two-element ranges. (left + right) / 2overflow. When both indices are nearINT_MAX, the sum overflows — undefined behavior in C.left + (right - left) / 2is the safe form (this exact bug lived in Java’s JDK binary search for nine years).- Using
<instead of<=in the merge comparison. The result is still sorted, but the sort is no longer stable — equal elements from the right half jump ahead of ones from the left. Stability is often the reason merge sort was chosen in the first place. - Forgetting the leftover loops. If one half empties first, the remaining elements of the other half must still be copied; dropping those loops silently loses data.
- Allocating temp arrays with VLAs.
int L[n1]works until someone sorts a million elements and the stack overflows. Usemalloc(andfree!) for buffers whose size depends on input.
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 same algorithm adapts to arrays (copy into temp buffers) and linked lists (relink pointers) — the data structure changes the cost model, not the idea
Frequently Asked Questions
Is merge sort faster than quick sort?
Usually not on arrays in RAM. Quick sort’s in-place partitioning is more cache-friendly, so it wins on average despite the same O(n log n) complexity. Merge sort wins when you need guaranteed worst-case O(n log n), stability, or you’re sorting linked lists or on-disk data.
Why is merge sort stable?
Because the merge takes from the left half on ties (L[i] <= R[j]). Elements that compare equal keep their original relative order. Change <= to < and stability is gone.
Can merge sort be done in-place with O(1) extra space?
For arrays, in-place merging exists in theory but is complex and slow in practice — every practical array implementation uses an O(n) buffer. For linked lists, merge sort genuinely is in-place: merging relinks pointers without copying data.
What is the recursion depth of merge sort?
⌈log₂ n⌉ — about 20 levels for a million elements, so stack overflow is not a concern (unlike a worst-case quick sort, which can recurse n levels deep). If you must avoid recursion entirely, use the bottom-up version above.
Is C’s qsort() a merge sort?
The C standard doesn’t say which algorithm qsort() uses, and it does not guarantee stability. glibc’s qsort() actually uses merge sort when memory allows, falling back to quick sort — but portable code must not rely on that. If you need stability in C, write merge sort yourself (there is no standard stable sort like C++’s std::stable_sort).
Related Programs
- Quick Sort in C
- Insertion Sort in C
- Heap Sort in C
- Bubble Sort in C
- Selection Sort in C
- Radix Sort in C
- Sort a Linked List in C
- Recursion in C — Complete Guide
- 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.