똑똑한 코드 작성을 위한 실전 알고리즘

164

똑똑한 코드 작성을 위한 실전 알고리즘

5.6

병합 정렬

앞서 살펴본 예제에서 영감을 받아 ‘배열을 정렬하기 위한 재귀적 분할 정복 접근이 있는가?’라

는 질문을 할 수 있다. [코드

5

-

6

]은 이런 의문에 대한 핵심을 보여준다. 배열을 정렬하기 위해

재귀적으로 왼쪽 반을 정렬하고 재귀적으로 오른쪽 반을 정렬한다. 그런 다음 전체 배열이 정

렬되도록 각각의 정렬된 결과를 병합한다.

코드

5-6

재귀적 정렬 개념 구현

def sort(A):

def rsort(lo, hi):

➊

if hi <= lo: return

➋

mid = (lo+hi) // 2

rsort(lo, mid)

➌

rsort(mid+1, hi)

merge(lo, mid, hi)

➍

rsort(0, len(A)-1)

➊

A[lo .. hi]

를 정렬하기 위한 재귀적인 메서드

➋

종료 조건 : 값이 한 개 이하인 범위는 이미 정렬되었다고 판단한다.

➌

재귀 조건 :

A

의 왼쪽 반과

A

의 오른쪽 반을 정렬한다.

➍

배열의 정렬된 두 반쪽을 병합한다.

[코드

5

-

6

]의 구조는 [코드

5

-

5

]에서 기술한

find

_

max

(

A

)

와 동일하다. 해당 구현을 완성하면

추가 저장 공간이 필요하지만 우리가 지향하는

O

(

N

log

N

) 성능으로 원본 배열에 정렬의 내용

을 바로 적용하는

병합 정렬

Merge

Sort

을 이끌어낼 ...