#include <stdio.h>
#define MAX_SIZE 100
void print_arry(int arry[], int n);
void merge_sort(int arry[], int start, int end);
void merge(int arry[], int start, int middle, int end);

int sorted_arry[MAX_SIZE] = {0, };

void main(void){

	int arry[MAX_SIZE]={5,10,7,15,20,3,14,21};
	int n=8;
	printf("º´·ÄÀü : ");
	print_arry(arry, n);
	merge_sort(arry, 0, n - 1);
	printf("º´·Ä : ");
	print_arry(sorted_arry, n);
	return;
}

void merge_sort(int arry[],int start,int end){
	int middle = (start + end) / 2;
	if (start < end){
		merge_sort(arry, start,middle);
		merge_sort(arry, middle + 1, end);
		merge(arry,start,middle,end);
	}
	return;
}
void merge(int arry[], int start, int middle, int end){
	int i;
	int left_point = start;
	int right_point = middle + 1;
	int insert_point = start;


	while (left_point <= middle &&right_point <= end){
		if (arry[left_point] <= arry[right_point]){
			sorted_arry[insert_point] = arry[left_point];
			left_point++;
		}
		else{
			sorted_arry[insert_point] = arry[right_point];
			right_point++;
		}
		insert_point++;
	}
	if (left_point > middle){
		for (i = right_point; i <= end; i++, insert_point++) sorted_arry[insert_point] = arry[i];
	}
	else {
		for (i = left_point; i <= middle; i++, insert_point++) sorted_arry[insert_point] = arry[i];
	}
	for (i = start; i <= end; i++) arry[i] = sorted_arry[i];
}

void print_arry(int arry[], int n){
	int i;
	for (i = 0; i < n; i++){
		printf("%d ", arry[i]);
	}
	printf("\n");
	return;
}