Merge Sort.cpp

#include <stdio.h>

// 병합 정렬(Merge Sort)
// 대표적인 '분할 정복' 방법을 채택한 알고리즘
// O(N * logN)을 보장
// 병합 정렬을 구현할 때 신경써야 하는 부분은 반드시 정렬에 사용되는 배열은 '전역 변수'로 선언해야 한다는 것
// 만약 함수 안에서 배열을 선언하게 된다면 매 번 배열을 선언해야 한단느 점에서 메모리 자원의 낭비가 매우 커질 수 있다.
// 이와 같이 기본적으로 병합 정렬은 '기존의 데이터를 담을 추가적인 배열 공간이 필요'하다는 점에서 메모리 활용이 비효율적이라는 문제가 존재

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

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 t = m; t <= n; t++) {
		a[t] = sorted[t];
	}
}

void mergeSort(int a[], int m, int n) {
	// 이외의 경우는 크기가 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(void) {
	int array[number] = { 7, 6, 5, 8, 3, 5, 9, 1 };
	mergeSort(array, 0, number - 1);
	for (int i = 0; i < number; i++) {
		printf("%d ", array[i]);
	}
}