Sorting

Merge Sort (Top-Down)

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

Algorithm

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;
}

The pinned input is [5, 1, 4, 2, 8]. The diagrams show the split into recursive halves, the sorted subarrays, and the final merge choices.

Step 1 - Split the input

The first midpoint splits [5, 1, 4, 2, 8] into left [5, 1] and right [4, 2, 8].

Top-down split used by merge_sort.[5,1,4,2,8]mid = 2[5,1]left[4,2,8]right

Step 2 - Sorted halves return

Recursive calls return [1, 5] and [2, 4, 8] before the final merge begins.

Returned subarrays before the final merge.sidebefore sortafter sortleft[5, 1][1, 5]right[4, 2, 8][2, 4, 8]

Step 3 - Merge by taking smaller fronts

Take 1 from left, then 2 and 4 from right, then the remaining 5 and 8.

Final merge produces [1, 2, 4, 5, 8].choiceleft frontright frontmergedtake 112[1]take 252[1, 2]take 454[1, 2, 4]extend58[1, 2, 4, 5, 8]

Complexity

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

Implementation notes

  • C stores int arr[] = {5, 1, 4, 2, 8} as a fixed local array in main; this source uses int n = 5 and calls merge_sort(arr, 0, n - 1).
  • merge_sort(int arr[], int left, int right) and merge(int arr[], int left, int mid, int right) receive the array as a pointer after parameter decay, so recursive calls mutate the original stack array.
  • Recursion stops at left >= right; mid = left + (right - left) / 2 keeps the bounds as signed int indexes for the small checked input.
  • Each merge call allocates int tmp[5] on that call's stack and uses i, j, and k to copy the smaller front value, preserving left-side ties with arr[i] <= arr[j].
  • Copy-back mutates the original array in order with arr[left + i] = tmp[i]. The trace shows [5, 1, 4, 2, 8], split as [5, 1] and [4, 2, 8], sorted to [1, 5] and [2, 4, 8], then merged to [1, 2, 4, 5, 8].
  • Output is formatted manually with printf("["), comma-separated printf("%d", arr[i]), and printf("]\n"). Visible memory is the original stack array, recursive stack frames, and per-merge stack buffers; there is no heap allocation.
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.