data-structures · intermediate · ~30 min
Recursive divide-and-conquer; the merge step on two sorted runs.
Implement void merge_sort(int *a, size_t n) that sorts a in non-decreasing order. You may allocate a scratch buffer with malloc.
Merge sort is the canonical divide-and-conquer algorithm and the basis for sorting linked lists, external sorts on huge files, and stable sorts in most language standard libraries.
Array a of n ints (n <= 100000).
a is sorted in place.
No qsort. O(n log n) time, O(n) auxiliary memory.
#include <stddef.h>
#include <stdlib.h>
void merge_sort(int *a, size_t n) { /* TODO */ }
Off-by-one when copying the right half back; forgetting to free the scratch buffer; merging in-place naively (which is O(n^2)).
n==0 and n==1 must early-return without allocating. Already-sorted and reverse-sorted inputs.
Time O(n log n) worst case. Space O(n) for the scratch buffer.
Solve this exercise in the browser editor — compile and run against the test harness, no setup required.