3병합 정렬에서의 재귀 호출

 

병합 정렬에서 ②번 과정을 보면 두 그룹으로 나눈 자료를 각각 정렬합니다. 그렇다면 나누어진 그룹은 어떤 정렬 알고리즘으로 정렬하는 걸까요?

바로 병합 정렬입니다. 병합 정렬을 하는 과정에서 나누어진 리스트를 다시 두 번의 병합 정렬로 정렬하는 것입니다.

이는 문제 8에서 살펴본, 원반이 n개인 하노이의 탑 문제를 풀기 위해 원반이 n-1개인 하노이의 탑 문제를 재귀 호출하는 것과 비슷합니다. 이렇게 어떤 문제를 푸는 과정 안에서 다시 그 문제를 푸는 것이 바로 재귀 호출의 묘미입니다.

여기서 재귀 호출의 세 가지 요건을 다시 떠올려 봅시다.

 

1 | 함수 안에서 자기 자신을 다시 호출합니다.

2 | 재귀 호출할 때 인자로 주어지는 입력 크기가 작아집니다.

3 | 특정 종료 조건이 만족되면 재귀 호출을 종료합니다.

 

병합 정렬은 자료 열 개를 정렬하기 위해 자료를 다섯 개씩 두 그룹으로 나누어 병합 정렬 함수를 재귀 호출합니다. 즉, 요건 1, 2는 쉽게 확인할 수 있습니다.

그렇다면 종료 조건은 어떨까요? 병합 정렬의 입력 리스트에 자료가 한 개뿐이거나 아예 자료가 없을 때는 정렬할 필요가 없으므로 입력 리스트를 그대로 돌려주면서 재귀 호출을 끝내면 됩니다.