Mergesort
Stable sorting.
Mergesort is a free C Academy lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the C Academy learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Stable Sorting
Mergesort is a divide-and-conquer sort that splits the array in half, sorts each half, then merges them back together. It is O(n log n) in every case and stable.
The Divide Step
Recursively split the array at the midpoint until each piece has one element. A single element is trivially sorted, which is the base case.
The Merge Step
The core operation merges two already-sorted runs into one. Walk both with index pointers, always copying the smaller front element next.
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i = lo, j = mid + 1, k = lo;
while (i <= mid && j <= hi)
tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
while (i <= mid) tmp[k++] = a[i++];
while (j <= hi) tmp[k++] = a[j++];
for (int t = lo; t <= hi; t++) a[t] = tmp[t];
}
int main(void) {
int a[] = {1, 4, 6, 2, 3, 5}; /* two sorted runs */
int tmp[6];
merge(a, 0, 2, 5, tmp);
for (int i = 0; i < 6; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Why It Is Stable
The merge uses a[i] <= a[j], so when two elements are equal it takes the one from the left run first. Since the left run held earlier elements, original order is preserved.
The Recursive Driver
Mergesort recurses on each half, then merges. We pass a shared scratch buffer to avoid allocating on every call.
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i=lo, j=mid+1, k=lo;
while (i<=mid && j<=hi) tmp[k++] = (a[i]<=a[j]) ? a[i++] : a[j++];
while (i<=mid) tmp[k++]=a[i++];
while (j<=hi) tmp[k++]=a[j++];
for (int t=lo;t<=hi;t++) a[t]=tmp[t];
}
void msort(int a[], int lo, int hi, int tmp[]) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
msort(a, lo, mid, tmp);
msort(a, mid + 1, hi, tmp);
merge(a, lo, mid, hi, tmp);
}
int main(void) {
int a[] = {5, 2, 9, 1, 3, 8, 4};
int tmp[7];
msort(a, 0, 6, tmp);
for (int i = 0; i < 7; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Memory Usage
Unlike quicksort, mergesort needs O(n) extra memory for the merge buffer. This is its main drawback for very large arrays in tight memory.
Guaranteed O(n log n)
The recursion always splits in half, giving log n levels, and each level merges n elements. So mergesort is O(n log n) in the best, average, and worst cases, unlike quicksort.
Counting Merge Levels
The number of recursion levels is ceil(log2 n). Let us compute it for several sizes.
#include <stdio.h>
int levels(int n) {
int L = 0;
while (n > 1) { n = (n + 1) / 2; L++; }
return L;
}
int main(void) {
int sizes[] = {1, 2, 8, 100, 1000};
for (int i = 0; i < 5; i++)
printf("n=%d levels=%d\n", sizes[i], levels(sizes[i]));
return 0;
}Bottom-Up Mergesort
An iterative variant merges runs of size 1, then 2, then 4, doubling each pass. It avoids recursion entirely and is friendly to linked lists.
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i=lo,j=mid+1,k=lo;
while(i<=mid&&j<=hi) tmp[k++]=(a[i]<=a[j])?a[i++]:a[j++];
while(i<=mid) tmp[k++]=a[i++];
while(j<=hi) tmp[k++]=a[j++];
for(int t=lo;t<=hi;t++) a[t]=tmp[t];
}
int main(void) {
int a[] = {5, 2, 9, 1, 3, 8}, n = 6, tmp[6];
for (int width = 1; width < n; width *= 2)
for (int lo = 0; lo < n - width; lo += 2 * width) {
int mid = lo + width - 1;
int hi = (lo + 2*width - 1 < n-1) ? lo + 2*width - 1 : n-1;
merge(a, lo, mid, hi, tmp);
}
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}When to Choose Mergesort
Prefer mergesort when you need:
- Guaranteed O(n log n), no bad cases
- Stability
- To sort linked lists (no random access needed)
- External sorting of data too big for RAM
Mergesort vs Quicksort
Quicksort is usually faster in practice and sorts in place, but is unstable with a bad worst case. Mergesort is stable with a guaranteed bound but uses extra memory. Choose based on your constraints.
Quick Check
Test your understanding of mergesort.
Recap
You learned mergesort.
- Divide in half, sort each, then merge
- The merge keeps left-first for equal keys, giving stability
- Guaranteed O(n log n) in all cases
- Costs O(n) extra memory; great for linked lists and external sorts
Frequently asked questions
Is the “Mergesort” lesson free?
Yes — the full text of “Mergesort” is free to read here on the web, and the C Academy course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the C Academy course, upgrade to CoddyKit PRO.
What will I learn in “Mergesort”?
Stable sorting. You practise C Academy with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start C Academy?
No prior experience is required. C Academy on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Mergesort” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this C Academy lesson?
Yes. Every C Academy lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.