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

#define MAX 1000

void p_a(int array[], int start, int end) {
    int k;

    for (k = start; k <= end; k++) {
	printf("%2d\n", array[k]);
    }
    printf("-----\n");
}

void merge(int array[], int s1, int e1, int s2, int e2) {
    int tmp[MAX / 2 + 1];
    int i, j, k;

    /* tmpにコピー */
    for (i = 0; i <= e1 - s1; i++) {
	tmp[i] = array[s1 + i];
    }
    for (i = 0, j = s2, k = s1; i <= e1 - s1 && j <= e2;) {
	if (tmp[i] < array[j]) {
	    array[k++] = tmp[i++];
	} else {
	    array[k++] = array[j++];
	}
    }
    /* 余りの処理 */
    while (i <= e1 - s1) {
	array[k++] = tmp[i++];
    }
}

void sort(int array[], int start, int end) {
    int half;

    printf("before sort\n");
    p_a(array, start, end);
    if (start >= end) {
	return;
    }
    half = start + (end - start) / 2;
    sort(array, start, half);
    sort(array, half + 1, end);
    merge(array, start, half, half+1, end);
    printf("after merge\n");
    p_a(array, start, end);
}

int main(int argc, char *argv[]) {
    int i, n, seed;
    int ar[MAX];

    if (argc <= 2) {
	printf("引数が足りません\n%s 配列の数 乱数の種\n", argv[0]);
	return 1;
    };
    n = strtol(argv[1], NULL, 10);
    if (n > MAX) {
	n = MAX;
    }
    seed = strtol(argv[2], NULL, 10);
    srandom(seed);
    for (i = 0; i < n; i++) {
	ar[i] = random() % 100;
    }
    printf("配列に乱数をセットしました。\n");
    sort(ar, 0, n - 1);
    printf("配列をソートしました。\n");
    return 0;
}