Merge sort

Challenge

Sort an array in place using merge sort (divide and conquer).

Task

Implement void merge_sort(int *a, size_t n) that sorts the n elements of a into non-decreasing order. You may allocate a scratch buffer with malloc.

Input

• a: writable array of n ints.
• n: the number of elements (up to 100000).

Output

Nothing returned; a[0..n-1] is sorted in place.

Example

{5,3,8,1,9,2,4,7,6,0}   ->   {0,1,2,3,4,5,6,7,8,9}
{42}                    ->   {42}

Edge cases

• n == 0 and n == 1 return immediately without allocating.
• Already-sorted and reverse-sorted inputs must still sort correctly.

Rules

• Do not call qsort. Implement the divide-and-conquer merge yourself in O(n log n) time, O(n) auxiliary memory.

Why this matters

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.

Input format

a: writable array of n ints (n <= 100000); n: element count.

Output format

Nothing returned; a is sorted non-decreasing in place.

Constraints

No qsort. O(n log n) time, O(n) auxiliary memory.

Starter code

#include <stddef.h>
#include <stdlib.h>
void merge_sort(int *a, size_t n) { /* TODO */ }

Common mistakes

Off-by-one when copying the right half back; forgetting to free the scratch buffer; merging in-place naively (which is O(n^2)).

Edge cases to handle

n==0 and n==1 must early-return without allocating. Already-sorted and reverse-sorted inputs.

Complexity

Time O(n log n) worst case. Space O(n) for the scratch buffer.

Background lessons

• Recursion — base case + smaller subproblem

Up next

• Heap sort
• Merge two sorted arrays