Sort - MergeSort

MergeSort는 분할 정복 알고리즘 중 하나이다. 배열을 절반으로 나누는 MergeSort를 재귀적으로 불러 각 크기가 1이 될 때까지 나눈다. 나눈 것들을 다시 하나의 배열로 만들면서 정렬한다.

Divide

Combine

 

MergeSort 과정

https://imgur.com/gallery/omL5k

MergeSort C Code

void merge(int* arr, int left, int mid, int right)
{
	int i, j, k;
	int n1 = mid - left + 1;
	int n2 = right - mid;
	int *L, *R;

	L = malloc(sizeof(int) * n1);
	R = malloc(sizeof(int) * n2);
	for (i = 0; i < n1; i++)
		L[i] = arr[left + i];
	for (j = 0; j < n2; j++)
		R[j] = arr[mid + 1 + j];

	i = 0;
	j = 0;
	k = left;
	while (i < n1 && j < n2) {
		if (L[i] <= R[j]) {
			arr[k] = L[i];
			i++;
		}
		else {
			arr[k] = R[j];
			j++;
		}
		k++;
	}
	while (i < n1) {
		arr[k] = L[i];
		i++;
		k++;
	}
	while (j < n2) {
		arr[k] = R[j];
		j++;
		k++;
	}
	free(L);
	free(R);
}

void merge_sort(int *arr, int left, int right)
{
	if (left < right)
	{
		int mid = (left + right) / 2;
		merge_sort(arr, left, mid);
		merge_sort(arr, mid + 1, right);
		merge(arr, left, mid, right);
	}
}

Merge Sort알고리즘의 특징

장점

• 데이터 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 정렬되는 시간은 O(nlog2n)으로 동일하다.
• 연결 리스트로 구성하면 링크 인덱스만 변경 되므로 데이터의 이동은 적어진다.

단점

• 배열로 구성하면 임시배열을 필요로 한다. 배열이 큰 경우 이동 횟수가 많아져 이동에 따른 시간적 낭비를 초래한다.

---

※참고 자료

www.geeksforgeeks.org/merge-sort/?ref=lbp