C++ 머지 소트(병합 정렬) 구현해보기

머지 소트 (MergeSort)

 

시간 복잡도 : O(n log n)

 

최선, 최악, 일반의 경우에 모두 동일한 시간 복잡도를 가짐

 

머지 소트의 경우 정렬하는 동안 동일한 길이의 배열이 하나 더 필요함

 

머지 소트는 동일한 값이 있을 때 순서가 보장되는 stable sort임

 

#include "stdafx.h"
#include <iostream>

int const ARRAY_COUNT = 8;

void PrintArray(int arr[], int start, int end, int pivot, int i, int j) {
	for (int k = 0; k < ARRAY_COUNT; k++) {
		std::cout << arr[k] << " ";
	}
	std::cout << "                 s:" << start << " e:" << end << " p:" << arr[pivot] << " i:" << i << " j:" << j << std::endl;
}

void Merge(int arr[], int left, int middle, int right) {
	PrintArray(arr, left, right, middle, 0, 0);
	int temp[ARRAY_COUNT] = { 0 };
	int l = left;
	int m = middle + 1;
	for (int i = left; i <= right; i++) {
		if (l <= middle && (arr[l] <= arr[m] || m > right)) {
			temp[i] = arr[l++];
		}
		else {
			temp[i] = arr[m++];
		}
	}
	for (int i = left; i <= right; i++) {
		arr[i] = temp[i];
	}
	PrintArray(arr, left, right, middle, 0, 0);
	std::cout << "-------------------------------------------------------" << std::endl;
}

void MergeSort(int arr[], int left, int right) {
	if (left >= right) {
		return;
	}
	int partition = (left + right) / 2;

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

int main()
{
	std::cout << "MergeSort" << std::endl;
	int arr[ARRAY_COUNT] = { 7, 5, 3, 8, 4, 1, 10, 2, /*9, 6 */ };
	MergeSort(arr, 0, ARRAY_COUNT - 1);
	for (int i = 0; i < ARRAY_COUNT; i++) {
		std::cout << arr[i] << " ";
	}
	return 0;
}

 

 

결과