マージソート

分割した要素を結合するときにはすでにミクロな集合内ではソートされていることが保証されているため線形時間で結合できる。というかんじ。

// merge_sort.c
#include "merge_sort.h"

void merge_sort(int *array, size_t size)
{
    int div = (int)size/2, *left = array, *right = &array[size - div - (size%2)];
    int result[size], i = 0, left_i = 0, right_i = 0;


    if (size > 1) {
        merge_sort(left, div);

        merge_sort(right, size - div);

        while(i < size) {

            if (right_i >= size - div) {
                result[i] = left[left_i];
                left_i++;
            }
            else if (left_i >= div) {
                result[i] = right[right_i];
                right_i++;
            }
            else {
                if (left[left_i] < right[right_i]) {
                    result[i] = left[left_i];
                    left_i++;
                }
                else {
                    result[i] = right[right_i];
                    right_i++;
                }
            }
            i++;
        }

        memcpy(array, result, sizeof(result));
    }
}

void print_r(const int list[], const size_t size)
{
    int i = 0;
    while(i < size) {
        printf("[%d] %d -> ", i, list[i]);
        i++;
    }
    printf("end \n");
}

// merge_sort.h
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void merge_sort(int *, size_t);
void print_r(const int [], const size_t);

// msort_test.c
#include "merge_sort.h"

int main()
{
    int test1[] = {5, 2, 3, 4, 8, 9, 7, 10, 2};

    print_r(test1, sizeof(test1)/sizeof(test1[0]));

    merge_sort(test1, sizeof(test1)/sizeof(test1[0]));

    print_r(test1, sizeof(test1)/sizeof(test1[0]));

    return 0;
}

[0] 5 -> [1] 2 -> [2] 3 -> [3] 4 -> [4] 8 -> [5] 9 -> [6] 7 -> [7] 10 -> [8] 2 -> end 
[0] 2 -> [1] 2 -> [2] 3 -> [3] 4 -> [4] 5 -> [5] 7 -> [6] 8 -> [7] 9 -> [8] 10 -> end