#include <stdio.h>

#include <stdlib.h>

#include <memory.h>

#include <time.h>



void printData(char*, int*, int);

void sort(int*, int);

void mergeSort(int*, int, int);

void mergeSortMain(int*, int, int);



/**

 * main

 */

int main() {

	int i;

	int dataNum; /* データの個数 */

	int divNum; /* データの分割数 */

	int* data; /* ソート元になるデータ */



	/* 前処理 */

	srand((unsigned int) time(NULL)); /* 疑似乱数系列の初期化 */

	

	/* ユーザーによるパラメータ入力 */

	printf("データの個数 = ");

	scanf("%d", &dataNum);

	printf("　　　分割数 = ");

	scanf("%d", &divNum);



	/* 入力されたデータのチェック */

	/* とりあえず正しく入力されているものとする... */



	/* データの生成 */

	data = (int*) malloc(sizeof(int) * dataNum); /* メモリの確保 */

	for (i = 0; i < dataNum; i++) {

		/* 0〜9 までのランダムな値を設定 */

		data[i] = rand() % 100;

	}

	printData("ソート前のデータ　　", data, dataNum);

	mergeSort(data, dataNum, divNum);

	printData("ソート後のデータ　　", data, dataNum);



	/* 後処理 */

	free(data); /* メモリの解放 */





	printf("適当な数値を入力すると終了します\n");

	scanf("%d", &divNum);



	/* 正常終了 */

	return 0;

}



/**

 * データを画面出力する

 * 入力: comment コメント

 *       data 出力対象のデータ配列

 *       size dataのサイズ

 */

void printData(char* comment, int* data, int size) {

	int i;

	printf("%s: ", comment);

	for (i = 0; i < size; i++) {

		printf("%02d ", data[i]);

	}

	printf("\n");

}



/**

 * dataの内容をバブルソートする

 * 入出力: data ソート対象のデータ配列

 *   入力: size dataのサイズ

 */

void sort(int* data, int size) {

	int i;

	int j;

	int temp;

	for (i = 1; i < size; i++) {

		for (j = 0; j < size - i; j++) {

			if (data[j] > data[j + 1]) {

				temp = data[j + 1];

				data[j + 1] = data[j];

				data[j] = temp;

			}

		}

	}

}



/**

 * 二つのデータ配列をマージする

 * 入力: src1 マージ対象のデータ

 *     : src2 マージ対象のデータ

 *     : size マージ対象のデータサイズ

 * 出力: dest マージ結果の出力先（サイズはsize * 2以上でなければならない）

 */

void merge(int* src1, int* src2, int size, int* dest) {

	int i1;

	int i2;

	int j;

	i1 = 0;

	i2 = 0;

	for (j = 0; j < size * 2; j++) {

		if ((i1 < size && src1[i1] < src2[i2]) || i2 >= size) {

			dest[j] = src1[i1++];

		} else {

			dest[j] = src2[i2++];

		}

	}

}



/**

 * dataの内容をマージソートする

 * ソート結果のマージを繰り返し結果を得る。

 * 入出力: data マージ対象のデータ配列（dataは一度divで分割されソートされていること）

 *   入力: size dataのサイズ

 *       : div データの分割数（sizeを割り切れる２の累乗の値であること）

 */

void mergeSortMain(int* data, int size, int div) {

	int* temp;

	if (div > 2) {

		/* divが２より大きい数字であれば半分ずつマージ処理を行う */

		mergeSortMain(&data[0], size / 2, div / 2);

		mergeSortMain(&data[size / 2], size / 2,  div / 2);

	}

	/* 二つのデータをマージする */

	/* 前処理 */

	temp = (int*) malloc(sizeof(int) * size);

	

	/* マージ */

	merge(&data[0], &data[size / 2], size / 2, temp);

	printData("マージ中のデータ　　", temp, size);



	/* 結果をdataに戻す */

	memcpy(data, temp, sizeof(int) * size);



	/* 後処理 */

	free(temp);

}



/**

 * dataの内容をマージソートする

 * dataをdivで分割し、分割結果をバブルソートする。

 * ソート結果のマージを繰り返し結果を得る。

 * 入出力: data ソート対象のデータ配列

 *   入力: size dataのサイズ

 *       : div データの分割数（sizeを割り切れる２の累乗の値であること）

 */

void mergeSort(int* data, int size, int div) {

	int i;



	/* 分割ソート */

	for (i = 0; i < div; i++) {

		sort(&data[(size / div) * i], size / div);

	}



	printData("分割ソート後のデータ", data, size);



	/* マージ処理 */

	if (div > 1) {

		mergeSortMain(data, size, div);

	}

}