[알고리즘] 병합 정렬 - C++

병합 정렬

---

#include <iostream>

using namespace std;

int temp[6];
int arr[] = { 4, 2, 6, 1, 5, 3 };

void merge(int start, int end) {
	int mid = (start + end) / 2;
	int i = start, j = mid + 1, k = start;

	while (i <= mid && j <= end) {
		if (arr[i] <= arr[j]) {
			temp[k] = arr[i];
			i++;
		}
		else {
			temp[k] = arr[j];
			j++;
		}
		k++;
	}
	
	if (i > mid) {	//i가 먼저 데이터를 모두 넣어서 j가 남았을 경우
		for (int a = j; a <= end; a++) {
			temp[k] = arr[a];
			k++;
		}
	}
	else {	//j가 먼저 데이터를 모두 넣어서 i가 남았을 경우
		for (int a = i; a <= mid; a++) {
			temp[k] = arr[a];
			k++;
		}
	}

	for (int a = start; a <= end; a++)	//정렬된 배열을 원래의 배열에 복사 
		arr[a] = temp[a];
}

void merge_sort(int start, int end) {
	if (start >= end) // 개수가 1개일 때
		return;
	int mid = (start + end) / 2;
	merge_sort(start, mid);
	merge_sort(mid + 1, end);
	merge(start, end);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);

	merge_sort(0, 5);

	for (int i = 0; i<6; i++) {
		cout << arr[i] << ' ';
	}

	return 0;
}

시간 복잡도: O(NlogN)