재귀함수를 이용한 병합정렬

재귀함수란, 자신을 재호출하는 함수이다.

예제

다음은 파이썬으로 병합정렬을 하는 재귀함수를 만든 것이다.

a 라는 리스트를 입력받아 병합정렬을 하는 함수이다.
(만약 이때 a의 길이가 1이하라면 정렬할 필요가 없으므로 a를 반환한다.)

지금 d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5] 라는 리스트가 입력되었다.

그럼 n = 10 이므로

mid = 5가 된다.
(만약 리스트의 길이가 5처럼 홀수라면 5//2 는 나머지를 버리고 몫만 계산하므로 g1은 [:2]까지,[2:]까지 출력한다.)

따라서 g1은 [ 6 , 8 , 3 , 9 , 10 ] , g2은 [ 1 , 2 , 4 , 7 , 5 ]이 되는 것이다.
계속 실행하면 [6],[8],[3],[9] .... 와 같이 만들어진다.

이제 결괏값이 들어갈 result를 빈 리스트로 만들어준다.

자, 이제 while 문이다.

while g1 and g2: 즉 g1와 g2안에 값이 있을 때,

if g1[0]<g2[0]: g1의 첫 번째 자리의 값이 g2의 첫번째 자리의 값보다 작다면

result.append(g1.pop(0)) g1의 첫 번째 자리의 값을 pop(끄집어내서) result.append(result의 끝자리에 추가한다)

이때 예제에서는 g1의 값이 6으로 8보다 더 작으므로
result에는 6이 추가된다.

그런데 이걸 반복하면 한쪽에 끝에 큰 숫자가 남기 마련이다.

이때 while g1: 을 실행한다.

g1이 있을 때, 남은 요소를 순서대로 끄집어내 result의 끝자리에 넣는 것이다.