[알고리즘] Merge 정렬

#include <stdio.h>

void mergeSort(int* arr, int left, int right);
void merge(int* arr, int left, int mid, int right);

int main(void)
{
	int arr[10] = { 1, 3, 5, 9, 7, 8, 2, 4, 6, 0 };

	for (int i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");

	mergeSort(arr, 0, 9);

	for (int i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");

	return 0;
}

void mergeSort(int* arr, int left, int right)
{
	if (left == right) { return; } // 각각의 배열로 분리가 되었다면 Return.
	int mid = (left + right) / 2; // mid 값을 기준으로 앞 뒤로 분리함.
	mergeSort(arr, left, mid); // mid 값 기준 앞을 분리.
	mergeSort(arr, mid + 1, right); // mid 값 기준 뒤를 분리.
	merge(arr, left, mid, right); // 분리해서 정렬된 걸, merge하면서 다시 정렬
	return;
}

void merge(int* arr, int left, int mid, int right) // arr의 주소값을 받아서 접근하기 때문에 void형을 반환.
{
	int i = left;
	int j = mid + 1;
	int k = left;
	int temp[10]; // max arr와 같은 배열이 필요함.

	while (i <= mid && j <= right) // i나, j가 index를 넘어갈 경우 while문에서 빠져나옴.
	{
		if (arr[i] < arr[j]) { temp[k++] = arr[i++]; } // i와 j를 비교해서, temp 배열에 작은순서대로 집어넣음.
		else { temp[k++] = arr[j++]; }
	}
	while (i <= mid) { temp[k++] = arr[i++]; } // 집어 놓고나면, 마지막 1개는 아직 들어가지 않았음. (while문 조건 때문에)
	while (j <= right) { temp[k++] = arr[j++]; } // 따라서 이 문장을 통해 마지막까지 전부 temp배열에 집어넣어줌.
	for (int a = left; a <= right; a++) { arr[a] = temp[a]; } // temp배열에서 arr로 옮기는 작업
	return;
}

 

Merge Sort 함수의 순서도.

-> Left = 0, Right = 7, Mid = 3 (Left, Mid)

        -> Left = 0, Right = 3, Mid = 1 (Left, Mid)

                -> Left = 0, Right = 1, Mid = 0 (Left, Mid)

                        -> Left = 0, Right = 0, Mid = 0 (Left, Mid) (Left < Right 조건으로 인한 Return)

                -> Left = 1, Right = 1, Mid = 1 (Left, Mid) (Left < Right 조건으로 인한 Return)

                -> Merge(0, 0, 1)

        -> Left = 2, Right = 3, Mid = 2 (Mid + 1, Right)

                -> Left = 2, Right = 2, Mid = 2 (Left, Mid) (Left < Right 조건으로 인한 Return)

        -> Merge(2, 2, 3)

-> Left = 4, Right = 7, Mid = 5 (Mid + 1, Right)

        -> Left = 4, Right = 5, Mid = 4 (Left, Mid)

                -> Left = 4, Right = 4, Mid = 4 (Left, Mid) (Left < Right 조건으로 인한 Return)

        -> Merge(4, 4, 5)

-> Merge(0, 3, 7)

 

 

Merge 함수에는 총 4번을 호출한다.

 

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

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

n log n의 보장된 시간을 얻을 수 있어서 많이 사용하는 알고리즘이다.