普通のマージソートなり.

merge_sort.c

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

void print_array(int * array, int size) {
    int i = 0;
    printf("{ ");
    while (1) {
        printf("%d", array[i]);
        if (++i >= size) {
            printf("}\n");
            break;
        } else {
            printf(",");
        }
    }
}

void merge(int *array, int begin, int end, int middle, int *buffer) {
    int i, j, k;
    for(i = begin; i <= middle; ++i) buffer[i] = array[i];
    for(i = middle + 1, j = end; i <= end; ++i, --j) buffer[i] = array[j];
    i = begin;  j = end;
    for(k = begin; k <= end; ++k) {
        if(buffer[i] <= buffer[j]){
            array[k] = buffer[i];
            ++i;
        }
        else{
            array[k] = buffer[j];
            --j;
        }
    }
}

void merge_sort_impl(int *array, int begin, int end, int* buffer) {
    int middle = (begin + end) / 2;
    if (begin >= end) {
        return;
    }
    merge_sort_impl(array, begin, middle, buffer);
    merge_sort_impl(array, middle + 1, end, buffer);
    merge(array, begin, end, middle, buffer);
}

void merge_sort(int *array, int size) {
    int *buffer = (int*)malloc(sizeof(int) * size);
    merge_sort_impl(array, 0, size - 1, buffer);
    free(buffer);
}

int main(void) {
    int i;
    int tests[4][5] = {
        { 1, 2, 3, 4, 5 },
        { 2, 3, 1, 4, 5 },
        { 5, 5, 5, 5, 5 },
        { 5, 2, 3, 4, 4 }
    };
    for (i = 0; i < 4; i++) {
        merge_sort(tests[i], 5);
        print_array(tests[i], 5);
    }
}