[Algorithm] Merge Sort (합병 정렬)

학회 스터디 강의할 때 다룬 문제

작년에 학교 수업에서 수를 정렬하는 게 과제로 나왔는데

O(nlogn) 정렬을 C언어로 구현해야 해서 오랜만에 Merge Sort를 짰었다.

그리고 또 오랜만에.

 

강의할 때 이거 잘 보여드리고 싶어서 ppt 되게 열심히 만들었는데

여기 그걸 다 첨부하기엔 양이 많고 또 워낙 유명한거니까 코드만 적어야겠다

 

int arr[1000000], sorted[1000000]; 	//전역변수. 벡터를 사용하면 더 간단하게 표현 가능
void Sort(int left, int right);		//정렬 함수
void Merge(int left, int right);	//Merge Sort  과정에서 분할한 두 배열을 합치는 함수
int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	Sort(0, n);

	for (int i = 0; i < n; i++) {
		cout << arr[i] <<  '\n';
	}
}

void Sort(int left, int right) {	//[left, right) 인덱스에 해당하는 구간의 수들 정렬
	if (!(right - left > 1)) {
		return;						//원소가 한 개 이하면 더 이상 분할하여 정렬할 필요 없다
	}

	int mid = (left + right) / 2;
	Sort(left, mid);						//두 부분으로 나눠 각각 정렬
	Sort(mid, right);
	Merge(left, right);						//정렬된 두 배열 합치기
}

void Merge(int left, int right) {
	int mid = (left + right) / 2;
	int leftIdx = left, rightIdx = mid;		//각각 왼쪽, 오른쪽 절반 배열의 인덱스
	int sortIdx = left;						//정렬 결과를 저장하는 배열의 인덱스

	for (; leftIdx < mid && rightIdx < right;) {	//두 배열 모두 원소가 남아있는 동안 확인
		if (arr[leftIdx] < arr[rightIdx]) {			//왼쪽 배열의 원소가 더 작은 경우
			sorted[sortIdx++] = arr[leftIdx++];	
		}
		else {					 					//오른쪽 배열의 원소가 더 작은 경우
			sorted[sortIdx++] = arr[rightIdx++]; 
		}
	}

	for (; leftIdx < mid; ) {			//비교 종료 후 왼쪽 절반에 남아있는 원소를 모두 복사
		sorted[sortIdx++] = arr[leftIdx++];
	}
	for (; rightIdx < right;) {			//비교 종료 후 오른쪽 절반에 남아있는 원소 모두 복사
		sorted[sortIdx++] = arr[rightIdx++];
	}

	for (int i = left; i < right; i++) {	//정렬된 내용을 기존 배열에 모두 복사하여 저장
		arr[i] = sorted[i];
	}
}