합병 정렬(Merge Sort)

<합병 정렬(Merge Sort)>

여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방법이다. 부분집합으로 분할(divide)하고, 각 부분집합에 대해서 정렬 작업을 완성(conquer)한 후에 정렬된 부분집합들을 다시 결합(combine)하는 분할 정복(divide and conquer) 기법을 사용한다.

 

[용어]

1. 분할(divide) : 입력 자료를 같은 크기의 부분집합 2개로 분할한다

2. 정복(conquer) : 부분집합의 원소들을 정렬한다.
부분집합의 크기가 충분히 작지 않으면 순환호출을 이용하여 다시 분할 정복 기법을 적용한다.

3. 결합(combine) : 정렬된 부분집합들을 하나의 집합으로 결합한다.

 

예)

정렬되지 않은 {69, 10, 30, 2, 16, 8, 31, 22}의 자료들을 병합 정렬 방법으로 정렬하는 과정을 살펴보자.
① 분할 단계 : 정렬할 전체 자료의 집합에 대해서 최소 원소의 부분집합이 될 때까지 분할작업을 반복하여 1개의 원소를 가진 부분집합 8개를 만든다.

② 병합단계 : 2개의 부분집합을 정렬하면서 하나의 집합으로 병합한다. 8개의 부분집합이 1개로 병합될 때까지 반복한다.

[코드]

Copyrightⓒ2014 By 한빛아카데미(주)