6. 병합(합병) 정렬 (Merge Sort)

Reference :
건국대학교 컴퓨터공학과 자료구조 수업 / 김성열 교수님

합병 정렬의 개념

: 하나의 리스트를 2 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것이다.

==> 합병 정렬은 분할 정복 (divide and conquer) 기법에 바탕을 두고 있다

 

분할 정복 (divide and conquer) 기법

: 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략

==> 분리된 문제가 아직도 해결하기 어렵다면 (충분히 작지 않다면) 분할 정복 방법을 연속하여 다시 적용

==> 분할 정복 기법은 대개 순환 호출을 이용하여 구현

 

1. 분할(Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다
2. 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법을 적용한다
3. 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 통합한다

ex)

==> 다음과 같은 배열이 있다고 가정하자

27 10 12 20 25 13 15 22

 

1. 분할(Divide) : 배열을 27 10 12 20 과 25 13 15 22의 2개의 부분배열로 나눈다
2. 정복(Conquer) : 부분배열을 정렬하여 10 12 20 27과 13 15 22 25를 얻는다
3. 결합(Combine) : 부분배열을 통합하여 10 12 13 15 20 22 25 27을 얻는다

---

합병 정렬 알고리즘

합병 정렬 알고리즘

merge_sort(list, left, right):

if left < right		//만약 나누어진 구간의 크기가 1이상이면
    mid = (left+right)/2;	//중간 위치를 계산한다
    merge_sort(list, left, mid);	//앞쪽 부분 배열을 정렬하기 위하여 merge_sort 함수를 순환 호출
    merge_sort(list, mid+1, right);	//뒤쪽 부분 배열을 정렬하기 위하여 merge_sort 함수를 순환 호출
    merge(list, left, mid, right);	//정렬된 2개의 부분 배열을 통합하여 하나의 정렬된 배열로 만든다.

합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계

 

 

1. 배열 A의 첫 번째 요소인 2와 B의 첫 번째 요소인 숫자인 1을 비교하여 1이 더 작으므로 1을 배열 C로 옮김
2. 다음으로 A의 2와 B의 다음 숫자인 3을 비교
3. 이번에는 A의 2가 B의 3보다 작으므로 이번에는 A의 2를 C로 이동
4. 이런 식으로 2개의 리스트 중에서 하나가 먼저 끝날 때 까지 이 과정을 되풀이
5. 두개의 리스트 중 하나가 먼저 끝나면 나머지 요소들을 리스트 C로 복사

 

합병 알고리즘

merge(list, left, mid, last):
// 2개의 인접한 배열 list[left..mid]와 list[mid+1..right]를 합병

i<-left;
j<-mid+1;
k<-left;

sorted 배열을 생성;
while i<=mid and j<=right do
	if(list[i]<list[j]
    	then
        	sorted[k]<-list[i]
            k++;
            i++;
        else
        	sorted[k]<-list[j]
            k++;
            j++;

위의 합병 알고리즘에서는 하나의 배열 안에 두 개의 정렬된 부분 리스트가 저장되어 있다고 가정

첫 번째 부분 리스트 : list[left] ~ list[mid]

두 번째 부분 리스트 : list[mid+1]~list[right]

합병된 리스트를 임시로 저장하기 위해 배열 sorted를 사용

---

합병 정렬의 C언어 구현

 

 

 

---

합병 정렬의 복잡도 분석