Merge sort.

merge_sort.c

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

void merge(int n, int m, int array[]) {
    int* tmp = malloc(sizeof(int) * n);
    int i = 0, l = 0, r = m;
    while(l < m && r < n) {
        tmp[i++] = array[l] < array[r] ? array[l++] : array[r++];;
    }
    while(l < m) tmp[i++] = array[l++];
    while(r < n) tmp[i++] = array[r++];
    for(int i = 0; i < n; ++i) {
        array[i] = tmp[i];
    }
    free(tmp);
}

void merge_sort(int n, int array[]) {
    if(n < 2) return;
    int m = n / 2;
    merge_sort(m, array);
    merge_sort(n - m, &array[m]);
    merge(n, m, array);
}

#define test(...) { \
    int array[] = { __VA_ARGS__ };          \
    int size = sizeof(array) / sizeof(int); \
    merge_sort(size, array);                \
    for(int i = 0; i < size; ++i) {         \
        printf("%d ", array[i]);            \
    }                                       \
    printf("\n");                           \
}

int main(void) {
    test(1, 2, 6, 9, 8, 3, 10, 7, 5, 4);
    test(7, 10, 2, 9, 1, 8, 5, 4, 6, 3);
    test(5, 10, 3, 8, 6, 4, 7, 1, 9, 2);
    test(3, 8, 10, 1, 9, 5, 7, 6, 2, 4);
    test(2, 1, 8, 5, 4, 10, 7, 6, 9, 3);
    test(6, 8, 3, 9, 5, 7, 2, 1, 10, 4);
    test(1, 2, 6, 5, 9, 4, 8, 3, 7, 10);
    test(1, 2, 8, 6, 5, 7, 10, 4, 3, 9);
    test(3, 5, 4, 6, 8, 2, 10, 9, 7, 1);
    test(9, 4, 3, 6, 1, 7, 2, 10, 8, 5);
    return 0;
}