Merge sort in C: solved exercise with divide and conquer

2026-02-26 4 minutes

Merge sort method in C

If you searched for a merge sort in C solved exercise, this version helps you understand the full idea, not only copy the code.

Merge sort is a recursive algorithm based on divide and conquer. It splits the problem into halves, sorts each half, then merges them. Its time complexity is O(n log n) in best, average, and worst case. It is commonly attributed to John von Neumann (1945) and is still a core example for efficient sorting design.

Merge sort strategy

The strategy is:

If the array has 0 or 1 element, it is already sorted.
If it has 2 or more elements, split it into two halves.
Sort each half recursively.
Merge the two sorted halves into one sorted array.

This keeps performance stable even when input order changes.

Merge sort pseudocode

function merge_sort(A, l, r, aux):
    if l >= r:
        return

    m = l + (r - l) / 2
    merge_sort(A, l, m, aux)
    merge_sort(A, m + 1, r, aux)
    merge(A, l, m, r, aux)

function merge(A, l, m, r, aux):
    i = l
    j = m + 1
    k = l

    while i <= m and j <= r:
        if A[i] <= A[j]:
            aux[k] = A[i]
            i = i + 1
        else:
            aux[k] = A[j]
            j = j + 1
        k = k + 1

    copy remaining left values
    copy remaining right values
    copy aux[l..r] back to A[l..r]

Problem statement

Implement merge sort to sort an integer array in ascending order.

C solution

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

static void merge(int a[], int aux[], int l, int m, int r) {
    int i = l;
    int j = m + 1;
    int k = l;

    while (i <= m && j <= r) {
        if (a[i] <= a[j]) {
            aux[k++] = a[i++];
        } else {
            aux[k++] = a[j++];
        }
    }

    while (i <= m) {
        aux[k++] = a[i++];
    }

    while (j <= r) {
        aux[k++] = a[j++];
    }

    for (i = l; i <= r; i++) {
        a[i] = aux[i];
    }
}

static void merge_sort_rec(int a[], int aux[], int l, int r) {
    if (l >= r) {
        return;
    }

    int m = l + (r - l) / 2;
    merge_sort_rec(a, aux, l, m);
    merge_sort_rec(a, aux, m + 1, r);
    merge(a, aux, l, m, r);
}

void merge_sort(int a[], int n) {
    if (n <= 1) {
        return;
    }

    int *aux = malloc((size_t)n * sizeof(int));
    if (!aux) {
        fprintf(stderr, "Error: could not allocate auxiliary memory\n");
        exit(EXIT_FAILURE);
    }

    merge_sort_rec(a, aux, 0, n - 1);
    free(aux);
}

int main(void) {
    int a[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(a) / sizeof(a[0]);

    merge_sort(a, n);

    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Expected output

3 9 10 27 38 43 82

Quick code walkthrough

merge_sort allocates one auxiliary array.
merge_sort_rec splits the range until single-element subarrays.
merge combines two already sorted halves in linear time.

Merge sort complexity in C

Time (best, average, worst): O(n log n)
Extra memory: O(n)

This is why merge sort is useful when you need predictable runtime and stable sorting behavior.

Common mistakes

Wrong bounds for each half (l, m, r).
Forgetting to copy merged values from aux back to a.
Using m = (l + r) / 2 without considering overflow on large indexes.
Missing the base case and causing infinite recursion.

Practical use

Merge sort is a good fit when:

you need stable sorting,
you need consistent performance,
you can spend extra memory for the auxiliary buffer.

If memory is your top constraint, quicksort may be a better fit in some scenarios.

Recommended next exercise

Guided practice and full book

If you want a complete path with progressive difficulty:

FAQ

Is merge sort in C useful for technical interviews?

Yes. It is common in interviews because it tests recursion, index handling, and complexity reasoning.

Does merge sort always run in O(n log n)?

Yes, in asymptotic time. That is one of its main advantages.

How should I practice merge sort effectively?

Start with small arrays, trace each merge step manually, then test duplicates, negatives, and reverse-sorted cases.