5. 병합 정렬

병합 정렬

병합 정렬은 분할 정복을 사용한 알고리즘 입니다. 퀵 정렬 같은 경우에도 분할 정복을 사용하지만 피벗 값에 따라서 최악의 경우 O(n²)의 시간 복잡도를 가질 수 있습니다. 하지만 병합 정렬의 경우 기본적으로 정확히 반으로 나누고 정렬하는 것이 핵심이므로 O(n*logn)의 시간 복잡도를 보장합니다. 이때 정렬해야할 갯수가 n개 일 때 모두 반으로 나눈 뒤 합치는 것을 반복하기에 logn의 단계수를 가지게 되고, 합칠 때 정렬하는 로직은 각각 배열에서 요소를 하나씩 비교해서 진행하여 n의 수행시간이 필요하므로 O(n*logn)의 시간복잡도를 보장하는 것입니다. 병합 정렬은 메모리 낭비를 줄이기 위해 정렬에 사용되는 배열을 전역 변수로 선언해야합니다. 그렇기에 O(n*logn)의 시간복잡도를 보장하지만 추가적인 배열 공간이 필요하므로 메모리 활용이 비효율적이라는 문제가 있습니다.

#include <stdio.h>

const int number = 1;
int sorted[number]; // 정렬 배열은 반드시 전역 변수로 선언

void merge(int a[], int m, int middle, int n) {
	int i = m;
	int j = middle + 1;
	int k = m;

	// 작은 순서대로 배열에 삽입
	while (i <= middle && j <= n) {
		if (a[i] <= a[j]) {
			sorted[k] = a[i];
			i++;
		}
		else {
			sorted[k] = a[j];
			j++;
		}
		k++;
	}

	// 남은 데이터도 삽입
	if (i > middle) {
		for (int t = j; t <= n; t++) {
			sorted[k] = a[t];
			k++;
		}
	}
	else {
		for (int t = i; t <= middle; t++) {
			sorted[k] = a[t];
			k++;
		}
	}

	// 정렬된 배열 삽입
	for (int i = m; i <= n; i++) {
		a[i] = sorted[i];
	}

}

void mergeSort(int a[], int m, int n) { // 재귀함수로 구현
	if (m >= n) {
		return;
	}

	// 크기가 1보다 큰 경우만
	if (m < n) {
		int middle = (m + n) / 2;
		mergeSort(a, m, middle);
		mergeSort(a, middle + 1, n);
		merge(a, m, middle, n);
	}
}

int main() {
	int numArray[number] = { 1 };
	mergeSort(numArray, 0, number - 1);

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

	return 0;
}