(c언어)병합정렬

리스트가 있을때 

2개씩 계속 쪼개고

2개씩 맞추어가며 정렬

또 2개씩 

마지막에 다합함

nlogn의 복잡도를 가짐

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define size 1000000

int sorted[size];

int merge(int list[],int left,int mid,int right ) {
	int i, j, k, l;
	i = left;
	j = mid + 1;
	k = left;
	while (i<=mid && j<=right) {
		if (list[i] <= list[j]) {
			sorted[k++] = list[i++];
		}
		else {
			sorted[k++] = list[j++];
		}
	
	}
	if (i > mid) {
		for (l = j; l<=right; l++) {
			sorted[k++] = list[l];
			
		}
	}
	else {
		for (l = i; l <= mid; l++) {
			sorted[k++] = list[l];
			
		}
	}
	for (l = left; l <= right; l++) {
		list[l] = sorted[l];
	}
	return 0;
}

int merge_sort(int list[],int left, int right) {

	int mid;
	if (left < right) {
		mid = (left + right) / 2;
		merge_sort(list, left, mid);
		merge_sort(list, mid + 1, right);
		merge(list, left, mid, right);
	}
	return 0;
}
int main(void) {
	int list[size];
	int a;
	scanf("%d", &a);

	for (int i = 0; i < a; i++) {
		scanf("%d", &list[i]);
	}
	merge_sort(list, 0, a-1);
	for (int i = 0; i < a; i++) {
		printf("%d\n", list[i]);
	}
	return 0;
}