<Algorithm,C++> Merge Sort (병합 정렬, 합병 정렬) 개념, 구현예제

Merge Sort 는 유명한 정렬 알고리즘 중에 하나입니다. 

 

최악의 시간복잡도가 O(n log n)라는 점 때문에 실제 알고리즘 문제에서도 많이 사용됩니다.

stable sort(안정 정렬, 같은 우선순위의 값에 대해 정렬 전후 순서 동일) , 메모리가 2배로 든다는 점이 특징입니다.

다른 개념적인 설명은 뒤로하고 여기선 오로지 외워서 사용하기 편한 방법을 하나 소개합니다.

 

톱다운으로 구현한 방법입니다.

 

#include <iostream>
#define MAX 10
int tmp[MAX];

using namespace std;

void mergeSort(int arr[], int s, int e)
{
	//base condition
	if (s >= e) return;

	//divide
	int m = (s + e) / 2;
	//conquer
	mergeSort(arr, s, m);
	mergeSort(arr, m + 1, e);

	//combine
	int idx1 = s, idx2 = m + 1, k=s;
	while ((idx1 <= m) && (idx2 <= e)) {
		if (arr[idx1] < arr[idx2]) tmp[k++] = arr[idx1++];
		else tmp[k++] = arr[idx2++];
	}
	while (idx1 <= m) tmp[k++] = arr[idx1++];
	while (idx2 <= e) tmp[k++] = arr[idx2++];

	//copy
	for (int i = s; i <= e; i++) arr[i] = tmp[i];
}

void printArr(int arr[]) {

	for (int i = 0; i < MAX; i++)cout << arr[i]<<" ";
	cout << "\n";
}

int main()
{
	int arr[MAX] = { 3,5,2,1,9,0,7,6,8,4 };
	cout << "origin : ";
	printArr(arr); //3 5 2 1 9 0 7 6 8 4

	mergeSort(arr,0,9);

	cout << "sorted : ";
	printArr(arr); //0 1 2 3 4 5 6 7 8 9
	return 0;
}