C언어의 병합정렬 (merge_sort) 알고리즘

초보자분들이 이해하시기에는 어려운 정렬 방법입니다. 

이 블로그에 있는 (선택, 삽입, 버블, 셀 정렬)을 먼저 이해하신 뒤에 보시는 것을 추천드립니다.

장점: 다른 정렬방법보다 수행 속도가 빠르고 효율적이다.

단점: 퀵 정렬과 다르게 <stdlib.h>에 구현되어 있지 않아서 직접 코드를 짜야 하는 불편함이 있다.

사용 방법: merge_sort(원본 배열,    정렬되어 저장될 배열,     첫 번째 인덱스,    마지막 인덱스)

void merge(int a[], int b[], int left, int right) {	// 병합 (분할된 세트를 정렬하면서 합침.)
	
	
	int l = left;	// 왼쪽 집합의 시작점
	int mid = (left + right) / 2;	// 왼쪽 집합의 마지막 지점
	int j = mid + 1;	// 오른쪽 집합의 시작점

	int compare = left;	// 정렬된 값을 b에 대입하기 위한 변수

	while (l <= mid && j <= right) {

		if (a[l] > a[j])	// 오른쪽이 더 작을 때 (바꿔서 저장)
			b[compare++] = a[j++];	// 오른쪽 값을 왼쪽에 저장
		
		else				// 왼쪽이 더 작을 때 (그대로 둠)
			b[compare++] = a[l++];	// 왼쪽 값을 왼쪽에 저장
	}


	while (l <= mid) {	// 중간보다 작을 때, 계속 돌아감.
		b[compare++] = a[l++];	// 아직 들어가지 않은 값을 마저 넣어줌.
	}


	while (j <= right){	// 끝보다 작을 때, 계속 돌아감.
		b[compare++] = a[j++];	// 아직 들어가지 않은 값을 마저 넣어줌.
	}

	for (int i = left; i <= right; i++)
		a[i] = b[i];	// 전체 요소를 돌면서 바뀐 값을 a에도 적용시켜준다.
	
}

void merge_sort(int a[], int b[], int left, int right) {	// 분할(작은 세트로 쪼갬) 및 병합
	
	int mid;	// 배열의 중간
	
	if(left < right) {
		
		// 0,1   2,3
		mid = (left + right) / 2;	// 중간 지점
		merge_sort(a, b, left, mid);		// 중간을 기준으로 왼쪽 분할
		merge_sort(a, b, mid + 1, right);	// 중간을 기준으로 오른쪽 분할
		merge(a, b, left, right);	// 왼쪽과 오른쪽을 정렬한 후 병합
	}
	
}