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

#define ARRAYSIZE 20

void mergesort(int*, int);

int main(void) {
	int array[ARRAYSIZE];
	//int * pArr = (int*)malloc(sizeof(int)* 100);
	
	srand(time(NULL));
	for (int i = 0; i < ARRAYSIZE; i++)
		array[i] = rand() % 100;

	for (int i = 0; i < ARRAYSIZE; i++) {
		printf("%d ", array[i]);
	}
	printf("\n");

	mergesort(array, ARRAYSIZE);

	for (int i = 0; i < ARRAYSIZE; i++) {
		printf("%d ", array[i]);
	}
	printf("\n");

	system("PAUSE");

	return 0;
}

void mergesort(int* arr, int size) {
	const int leftsize = (size + 1) / 2;

	if (size <= 1) return;

	mergesort(arr, leftsize);
	mergesort((arr + leftsize), size/2);

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


	int a = 0, b = 0;
	// 작은 숫자 찾기(한 쪽이 소진될 때까지)
	while (a != (size + 1) / 2 && b != size / 2) {
		if (arr[a] < arr[b + leftsize]) {
			temp[a + b] = arr[a];
			a++;
		}
		else {
			temp[a + b] = arr[b + leftsize];
			b++;
		}
	}
	// 뒷처리
	if (a == (size + 1) / 2) {
		while ((a + b) < size) {
			temp[a + b] = arr[leftsize + b];
			b++;
		}
	}
	else {
		while ((a + b) < size) {
			temp[a + b] = arr[a];
			a++;
		}
	}

	// 덮어쓰기
	for (int i = 0; i < size; i++)
		arr[i] = temp[i];

	// 메모리 누수 방지
	free(temp);
}