[C++][구현] 합병 정렬 (Merge Sort)

⭐ 합병 정렬 (Merge Sort)

 

크게 나누는 Split부분

 

합치는 merge 부분이 있습니다.

 

split 부분에서는 재귀적(reculsive) 방법을 이용하여 나눠진 개수가 1개가 될 때 까지 나눠줍니다.

 

이 후, begin Index와 last Index를 이용하여, merge를 해줍니다.

 

각각 비교를 해가며, 작은 수 부터 vector에 임시 저장한 후

 

반복문이 끝난 후 그 임시저장 한 vector를 다시 배열에 재배치 시켜줍니다.

 

이를 반복하면 정렬이 완성이 됩니다.

---

#include <iostream>
#include <vector>
using namespace std;

void mergeSort(int nums[], int beginIdx, int lastIdx) { // O(nlgn)
	vector<int> tmp;

	if (beginIdx < lastIdx) {
		// Split
		int mid = (beginIdx + lastIdx)/2;
		mergeSort(nums, beginIdx, mid);
		mergeSort(nums, mid + 1, lastIdx);
		
		// Merge
		int left_side_size = mid - beginIdx + 1;
		int right_side_size = lastIdx - mid;

		int left_side_Idx = beginIdx;
		int right_side_Idx = beginIdx + left_side_size;

		while (left_side_Idx < beginIdx + left_side_size && right_side_Idx < lastIdx + 1) {
			if (nums[left_side_Idx] < nums[right_side_Idx]) {
				tmp.push_back(nums[left_side_Idx]);
				left_side_Idx++;
			}
			else {
				tmp.push_back(nums[right_side_Idx]);
				right_side_Idx++;
			}
		}

		while (right_side_Idx < lastIdx + 1) {
			tmp.push_back(nums[right_side_Idx++]);
		}
		while (left_side_Idx < beginIdx + left_side_size) {
			tmp.push_back(nums[left_side_Idx++]);
		}

		// 배열에 정렬된 값 넣어주기
		for (int i = 0; i < (left_side_size + right_side_size); i++) {
			nums[beginIdx + i] = tmp[i];
		}
	}
}

int main() {
	int nums[6] = { 0, 4, 2, 3, 7, 6 };
	mergeSort(nums, 0, 5);

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

}

 

시간복잡도는 O(nlgn) 이고, stable한 정렬 방법입니다.