Merge Sort in C: Stable Merge and Allocation Safety

Merge sort in C divides an array, sorts both halves, and merges them in order. This program allocates one reusable buffer, checks allocation-size overflow and failure before modifying the array, and chooses the left value first on ties to preserve stability.

Complete program with checked allocation

#include <stdio.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

static void sort_range(int values[], int buffer[], size_t low, size_t high) {
    if (high - low < 2) return;
    size_t mid = low + (high - low) / 2;
    sort_range(values, buffer, low, mid);
    sort_range(values, buffer, mid, high);
    size_t left = low, right = mid, out = low;
    while (left < mid && right < high) {
        buffer[out++] = values[left] <= values[right] ? values[left++] : values[right++];
    }
    while (left < mid) buffer[out++] = values[left++];
    while (right < high) buffer[out++] = values[right++];
    for (size_t i = low; i < high; ++i) values[i] = buffer[i];
}

int merge_sort(int values[], size_t count) {
    if (count < 2) return 1;
    if (count > SIZE_MAX / sizeof *values) return 0;
    int *buffer = malloc(count * sizeof *buffer);
    if (buffer == NULL) return 0;
    sort_range(values, buffer, 0, count);
    free(buffer);
    return 1;
}

int main(void) {
    int values[] = {64, 34, 25, 12, 22};
    size_t count = sizeof values / sizeof values[0];
    if (!merge_sort(values, count)) {
        fputs("Unable to allocate merge buffer.\n", stderr);
        return 1;
    }
    for (size_t i = 0; i < count; ++i) printf("%s%d", i ? " " : "", values[i]);
    putchar('\n');
    return 0;
}

12 22 25 34 64

Split and merge trace

During the final merge, compare heads 34 and 12, then 34 and 22, then 34 and 25. After copying 12, 22 and 25, the right half is exhausted and the remaining 34 and 64 are copied. The loop copies only within [low, high). The temporary merged range is then copied back before its parent's merge starts.

Why this merge is stable

The <= comparison selects the left record on equal keys. Since each half was itself sorted stably, equal-key records retain their original relative order throughout the merges. If records 2a 1 2b are sorted by numeric key, the order becomes 1 2a 2b. An integer-only output test cannot demonstrate identity preservation; the tie rule is the key argument. For a small stable in-place alternative, trace insertion sort.

Allocation failure and array contract

merge_sort returns 1 on success and 0 when the buffer size is unrepresentable or allocation fails. The array is unchanged on either failure path because both checks happen before sorting. The caller must check the result: ignoring it can cause later code to assume an unsorted array is sorted. All successful allocated paths free the buffer exactly once.

Positive counts require count writable integers. Count zero permits a null pointer; zero or one element needs no allocation. The size-overflow guard protects the allocation calculation, not a caller that lies about the array's real length. This is a conventional hosted-memory example, not a promise that allocation is suitable in an interrupt handler or small firmware system.

Time and space costs

This version does O(n log n) work for best, average and worst inputs with n greater than one; it does not include an already-sorted shortcut. It requires O(n) buffer storage plus O(log n) recursive call-stack space. Total auxiliary space is O(n), not O(1), and a linked-list merge sort has different trade-offs. Allocation is performed once, not at every split.

Quick sort avoids the linear buffer but has a quadratic worst case in the teaching implementation. Heap sort guarantees O(n log n) with constant auxiliary array storage but is not stable. Compare all methods in the sorting guide.

Practice and common bugs

For 4 1 3 2, the two sorted halves are 1 4 and 2 3; the merge yields 1 2 3 4. Try a singleton, negatives, duplicate values, ascending/reverse order and integer extremes. No stdin is needed. Do not allocate count bytes when count is a number of integers; use count * sizeof *buffer only after checking for overflow. Omitting either leftover-copy loop drops values when one half ends early.

Does sorting in place mean no extra memory?

This function changes the caller's array, but it is not an in-place O(1)-space algorithm: it still uses a separate linear buffer. State both properties rather than treating them as synonyms.