[알고리즘] 병합 정렬(Merge Sort)

병합 정렬(Merge Sort)

특징

1. 안정 정렬(Stable Sort): 동일한 값에 대해 상대적인 순서가 유지됩니다. 즉, 동일한 값의 원소들은 입력 배열에서의 순서와 동일한 순서로 정렬됩니다.
2. 분할 정복(Divide and Conquer): 큰 문제를 작은 문제로 분할하여 해결하는 방식을 사용합니다.
3. 추가적인 메모리 사용: 임시 배열을 사용하여 원소들을 병합하는 과정에서 추가적인 메모리가 필요합니다.
4. 평균적으로 빠른 속도: 평균 시간 복잡도가 O(n log n)으로 매우 효율적입니다.
5. 비교 기반 정렬(Comparison Sort): 원소들의 상대적인 크기를 비교하여 정렬합니다.

알고리즘 동작 방식

1. 주어진 배열을 반으로 분할합니다.
2. 분할된 부분 배열에 대해 재귀적으로 병합 정렬을 수행합니다.
3. 분할된 부분 배열들을 병합하여 정렬된 하나의 배열로 합칩니다.
4. 정렬된 배열을 반환합니다.

장점

1. 안정 정렬이므로 동일한 값의 원소들의 상대적인 순서가 유지됩니다.
2. 평균 시간 복잡도가 O(n log n)으로 매우 효율적입니다.
3. 입력 배열의 크기에 무관하게 일정한 성능을 보입니다.
4. 추가적인 메모리를 사용하여 배열을 병합하는 과정을 수행하기 때문에 원본 데이터가 손상되지 않습니다.

단점

1. 추가적인 메모리가 필요합니다. 병합하는 과정에서 임시 배열을 사용하기 때문에 입력 배열과 같은 크기의 추가적인 메모리가 필요합니다.
2. 재귀 호출을 사용하기 때문에 스택 메모리를 많이 사용할 수 있습니다.
3. 제자리 정렬이 아니므로 입력 배열 이외의 공간이 필요하다는 점에 유의해야 합니다.

요약

병합 정렬은 안정적이고 효율적인 정렬 알고리즘으로, 평균 시간 복잡도가 O(n log n)입니다.

추가적인 메모리 사용이 필요하며, 입력 배열의 크기에 무관하게 일정한 성능을 보입니다.

그러나 재귀 호출과 추가적인 메모리 사용으로 인해 일부 상황에서는 다른 알고리즘보다 공간과 성능 면에서 불리할 수 있습니다.

https://levelup.gitconnected.com/sorting-algorithms-selection-sort-bubble-sort-merge-sort-and-quicksort-75479f8f80b1

void DoMergeSort()
{
	vector<int> arr;
	arr.assign(rand() % 30, int());

	for (auto& num : arr)
		num = rand() % 100;

	cout << "Before Sort" << endl;

	for (auto num : arr)
		cout << num << " ";BubbleSort

	cout << endll << "After Sort" << endl;

	MergeSort(arr, 0, arr.size() - 1);
	for (auto num : arr)
		cout << num << " ";

	cout << endll;

	Pause;
	return;
}

void MergeSort(vector<int>& arr, int left, int right)
{
	if (left >= right) return;

	int mid = (left + right) / 2;

	MergeSort(arr, left, mid);
	MergeSort(arr, mid + 1, right);
	Merge(arr, left, mid, right);
}

void Merge(vector<int>& arr, int left, int mid, int right)
{
	int leftIndex = left;		// 왼쪽 부분 리스트의 시작 인덱스
	int rightIndex = mid + 1;	// 오른쪽 부분 리스트의 시작 인덱스
	int resultIndex = left;		// 결과를 저장할 배열의 인덱스
	int size = right + 1;		// 임시 배열 사이즈
	vector<int> temp;			// 병합 결과 저장할 임시 배열

	temp.assign(size, int());

	// 왼쪽 부분 리스트와 오른쪽 부분 리스트의 요소들을 비교하며 임시 배열에 병합
	while (leftIndex <= mid && rightIndex <= right)
	{
		if (arr[leftIndex] >= arr[rightIndex])
			temp[resultIndex++] = arr[leftIndex++];
		else
			temp[resultIndex++] = arr[rightIndex++];
	}

	// 왼쪽 부분 리스트나 오른쪽 부분 리스트의 요소 중 하나가 모두 병합된 경우,
	// 남은 요소들을 임시 배열에 추가
	while (leftIndex <= mid)
		temp[resultIndex++] = arr[leftIndex++];
	while (rightIndex <= right)
		temp[resultIndex++] = arr[rightIndex++];

	// 임시 배열에 저장된 병합 결과를 원래 배열에 복사
	for (int i = left; i <= right; i++)
		arr[i] = temp[i];

	temp.clear();
}