[정렬] 병합정렬 ( Merge Sort )

void merge(vector<int>& v, int left, int mid, int right) {
	int i, j, k, l;
	i = left; j = mid + 1; k = left;
	while (i <= mid && j <= right) {
		if (v[i] <= v[j]) sorted[k++] = v[i++]; //더 작은 값을 새로운 배열로 할당
		else sorted[k++] = v[j++];
	}
	if (i > mid)// mid 값을 넘었으므로 right까지의 남은 j 원소들을 새로운배열에 옮김
		for (l = j; l <= right;l++) sorted[k++] = v[l];
	else for (l = i;l <= mid;l++) sorted[k++] = v[l];//j > right
	for (l = left; l <= right;l++) v[l] = sorted[l];// 새로운 배열을 다시 원래배열로 옮김
	return;
}

void mergeSort(vector<int>& v, int left, int right) {
	int mid = (left + right) / 2; 
	if (left < right) {
		mergeSort(v, left, mid);
		mergeSort(v, mid + 1, right);
		merge(v, left, mid, right);
	}
}

시간 복잡도

평균 시간복잡도 = O(nlogn)

 

제자리성 : 제자리 x (추가 배열 사용)

 

알고리즘 

1. left, right의 중간인 mid 값 설정

2. i, j 를 증가시키면서 각 인덱스의 비교를 통해 더 작은 값을 sorted 배열에 삽입

3. 먼저 끝나는 쪽의 반대쪽에서 남은 부분은 sorted 에 순서대로 삽입