C言語で書いてみました

■ マージソート（平成16年春期午後問4）

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

/* 基本情報 平成16年春期午後問4 */
/* マージソート */
#define true    1
#define false   0

void print_array(int *a, int size)
{
    int i;
    for (i = 0; i < size - 1; i++)
        printf("%d,", *(a+i));
    printf("%d\n", *(a+size-1));
}

void mergeSort(int input[], int output[], int size)
{
    int span_size, *temp, span_idx, write_idx, a_idx, b_idx;
    int a_yet, b_yet, ordered;
    int i;
    temp = (int *)malloc(size / 2);
    /* 併合対象領域の大きさ */
    span_size = 2;
    /* 配列のコピー */
    for (i = 0; i < size; i++)
        output[i] = input[i];
    while (span_size <= size) {
        print_array(output, size);
        /* 入力領域のインデックスの初期化 */
        span_idx = 0;
        /* 出力領域のインデックスの初期化 */
        write_idx = 0;
        ordered = true;
        while (span_idx < size) {
            a_idx = span_idx;
            b_idx = span_idx + span_size / 2;
            for (i = a_idx - span_idx; i < b_idx - a_idx; i++)
                temp[i] = output[i + span_idx];
            a_yet = true;
            b_yet = true;
            while (a_yet == true || b_yet == true) {
                if (b_yet == false || 
                    (a_yet == true && b_yet == true &&
                    temp[a_idx - span_idx] <= output[b_idx]))
                {
                    output[write_idx] = temp[a_idx - span_idx];
                    a_idx++;
                    if (a_idx >= span_idx + span_size / 2)
                        a_yet = false;
                } else {
                    output[write_idx] = output[b_idx];
                    b_idx++;
                    if (b_idx >= span_idx + span_size)
                        b_yet = false;
                }
                if (write_idx > 0) {
                    if (output[write_idx - 1] > output[write_idx])
                        ordered = false;
                }
                write_idx++;
            }
            span_idx += span_size;
        }
        if (ordered == true)
            span_size = size;
        span_size *= 2;
    }
    free(temp); 
}

int main()
{
    int input1[8] = { 47,33,68,55,74,89,25,10 };
    int input2[8] = { 2,1,4,3,8,7,6,5 };
    int output[8];
    mergeSort(input1, output, 8);
    print_array(output, 8);
    mergeSort(input2, output, 8);
    print_array(output, 8);
    return 0;
}