Merge Sort (Top-Down)

Split the array recursively, sort each half, then merge two sorted runs into one sorted result.

Algorithm

The checked-in replay follows the same small input and final output across all 21 DSA books, so this C DSA implementation can be compared directly with the other languages.

Basic Implementation

basic.c

#include <stdio.h>

void merge(int arr[], int left, int mid, int right) {
    int tmp[5];
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
        else tmp[k++] = arr[j++];
    }
    while (i <= mid) tmp[k++] = arr[i++];
    while (j <= right) tmp[k++] = arr[j++];
    for (i = 0; i < k; ++i) arr[left + i] = tmp[i];
}

void merge_sort(int arr[], int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    merge_sort(arr, left, mid);
    merge_sort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

int main(void) {
    int arr[] = {5, 1, 4, 2, 8};
    int n = 5;
    merge_sort(arr, 0, n - 1);
    printf("[");
    for (int i = 0; i < n; ++i) {
        if (i > 0) printf(", ");
        printf("%d", arr[i]);
    }
    printf("]\n");
    return 0;
}

Complexity

Time: O(n log n)
Space: O(n)
Stable: yes

Implementation notes

Keep the explicit algorithmic steps instead of calling a standard-library sort. The replay is meant to expose comparisons, movement, and recursion.
The implementation is intentionally compact for learning and replay, not a production sorting utility.

divide and conquer Each recursive call solves a smaller sorted subproblem.

merge step Two sorted halves are combined by repeatedly taking the smaller front item.