5. 합병 정렬 (Merge Sort)

<간략 버전>

#include <iostream>
using namespace std;
int arr[8] = { 21, 10, 12, 20, 25, 13, 15, 22 }, sorted[100];
void mergeSort(int st, int en){
    if (st >= en) return;
    int mid = (st + en) / 2;
    mergeSort(st, mid);
    mergeSort(mid + 1, en);
    int i = st, j = mid + 1;
    for (int k = st; k <= en; k++){
        if ((i <= mid && arr[i] < arr[j]) || j > en) sorted[k] = arr[i++];
        else sorted[k] = arr[j++];
    }
    for (int k = st; k <= en; k++) arr[k] = sorted[k];
} 
int main(){
    mergeSort(0, 7);
    for (int i = 0; i < 8; i++) cout << sorted[i] << " ";
    return 0;
}

#include <iostream>
using namespace std;
int sorted[8] = { 0 }; //합병을 위해 정렬하는 배열 만들어줌

void merge(int arr[], int left, int center, int right) {
	int start = left, middle = center + 1;
	int n = left;

	while (start <= center && middle <= right) { //두 배열 원소끼리 비교하여 작은 값부터 sorted에 넣어준다
		if (arr[start] <= arr[middle]) {
			sorted[n] = arr[start];
			start++;
		}
		else {
			sorted[n] = arr[middle];
			middle++;
		}
		n++;
	}

	if (start <= center) { //아직 다 안담긴 원소들이 남았을 경우
		for (int i = start; i <= center; i++) {
			sorted[n] = arr[i];
			n++;
		}
	}
	else if (middle <= right) {
		for (int i = middle; i <= right; i++) {
			sorted[n] = arr[i];
			n++;
		}
	}

	for (int i = left; i <= right; i++)arr[i] = sorted[i]; //정렬된 배열을 원래 배열에 넣어준다
}

void mergeSort(int arr[], int start, int end) { //합병 정렬
	if (start < end) { //원소의 개수가 2개 이상일 때만
		int middle = (start + end) / 2;
		mergeSort(arr, start, middle);
		mergeSort(arr, middle + 1, end);
		merge(arr, start, middle, end); //두 배열이 정렬이 된 상태에서 나중에 합침
	}
}

int main() {
	int arr[8] = { 21, 10, 12, 20, 25, 13, 15, 22 };
	int N = 8;

	mergeSort(arr, 0, N - 1);
	
	for (int i = 0; i < N; i++)cout << arr[i] << "\n";

	return 0;
}