[Sort] Merge Sort

- 대표적인 "분할정복" 방법을 채택한 알고리즘

- 퀵 정렬의 보완된 버전

   -> 퀵 정렬은 피벗 값에 따라서 편향되게 분할할 가능성이 있다는 점에서 최악의 경우 O(N^2)

   -> 하지만 일반적인 경우에서 퀵정렬보다는 느리다. 합병 정렬은 "배열을 생성하는" 시간이 있기 때문이다.

       정렬하고자 하는 배열의 길이가 길면 길수록 차이가 난다.

- Stable Sorting

- 최선/최악/평균 시간 복잡도 : O(nlogn)

 

자세한 내용은 

 

https://blog.naver.com/ndb796/221227934987

7. 병합 정렬(Merge Sort)

 

여기서 복습하는 것으로.

 

void merge(int arr[], int left, int mid, int right) {

	int i = left;
	int j = mid + 1;
	int k = left; // temp 배열의 인덱스

	while (i <= mid && j <= right) {
		if (arr[i] < arr[j]) {
			temp[k] = arr[i];
			i++;
		}
		else { 
			temp[k] = arr[j];
			j++;
		}
		k++;
	}

	if (i > mid) {
		//왼쪽 배열이 다 들어간 경우
		for (int t = j; t <= right; t++) {
			temp[k] = arr[t];
			k++;
		}
	}
	else {
		//오른쪽 배열이 먼저 다 들어간 경우
		for (int t = i; t <= mid; t++) {
			temp[k] = arr[t];
			k++;
		}
	}

	for (int z = 0; z <= right; z++) {
		arr[z] = temp[z];
	}

}

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);
	}

}