Merge

// 병합정렬 분할 함수 
void MergeSort(int arg[], int left, int right) {
	int mid;
	if (left < right) {
		mid = (left + right) / 2;			// 분할 함수의 중앙 찾기 
		MergeSort(arg, left, mid);		// 병합정렬 왼쪽 부분 
		MergeSort(arg, mid + 1, right);	// 병합정렬 오른쪽 부분 
		Merge(arg, left, mid + 1, right);	// 병합정렬 병합 하기 
	}
}

처음 매개변수 arg[]는 정렬되지 않은 배열을 받는다.

left는 시작 index, right은 끝 index를 입력받는다.

그러면 if문 조건에 만족하고

절반으로 분할한다.

즉, left와 right은 분할된 배열의 시작과 끝을 의미한다.

if문 조건이 만족하지 않는 순간에 다다르면 MergeSort를 종료하고

Merge를 실행한 후 복귀하면서 정렬한다.

Merge 부분에선 분산된 배열의 범위만큼 정렬하며 배열을 합친다.

// 병합정렬 병합/합병 함수 
void Merge(int arr[], int left, int mid, int right) {
	int temp[10] = { 0, };
	int index = left;
	int low = left;
	int high = mid;

	while ((low < mid) && (high <= right)) {
		if (arr[low] < arr[high]) {
			temp[index] = arr[low];
			low++;
		}
		else {
			temp[index] = arr[high];
			high++;
		}
		index++;
	}

	if (low < mid) {
		for (low = low; low < mid; low++, index++) {	// 앞쪽 배열에 남은것 모두 가져오기
			temp[index] = arr[low];
		}
	}
	if (high <= right) {
		for (mid = high; mid <= right; mid++, index++) {	// 뒤쪽 배열에 남은것 모두 가져오기
			temp[index] = arr[mid];
		}
	}

	for (index = left; index <= right; index++) {
		arr[index] = temp[index];
	}
	Display(arr, 10);
}

Quick