합병 정렬

 

: 분할 정복 알고리즘

: 2개의 부분 문제로 분할 -> 부분 문제의 크기가 1/2로 감소

 

n개의 숫자들을 n/2씩 2개의 부분문제로 분할

-> 각각의 부분 문제를 순환으로 합병 정렬

-> 2개의 정렬된 부분을 합병하여 정렬(정복)

 

즉, 정복 과정이 합병이다.

 

알고리즘

 

A와 B를 앞 숫자부터 비교 -> 더 작은 것 선택 -> 반복

MergeSort(A,p,q)
입력: A[p]~A[q]
출력: 정렬된 A[p]~A[q]
	if(p<q){
    	k=[(p+q)/2] //내림값
        MergeSort(A,p,k)
        MergeSort(A,k+1,q)
        A[p]~A[k]와 A[k+1]~A[q]를 합병
    }

 

void merge_sort(int list[], int left, int right)
{
	int mid;
    if(left<right)
    {
    	mid = (left+right)/2;
        merge_sort(list, left, mid);
        merge_sort(list, mid+1, right);
        merge(list, left, mid, right);
    }
}

int sorted[MAX_SIZE]; //결과 임시저장을 위해 추가 공간이 필요
//i=정렬된 왼쪽 리스트에 대한 인덱스
//j=정렬된 오른쪽 리스트에 대한 인덱스
//k=정렬된 sorted 리스트에 대한 인덱스

void merge(int list[], int left, int mid, int right)
{
	int i,j,k,l;
    i=left; j=mid+1; k=left;
    //분할 정렬된 list의 합병
    while(i<=mid && j<=right){
    	if(list[i]<=list[j])
        	sorted[k++]=list[i++];
        else
        	sorted[k++]=list[j++];
    }
    if(i>mid) //남아 있는 레코드 일괄 복사
    	for(l=j;l<=mid;l++)
        	sorted[k++]=list[l];
    else
    	for(l=i;l<=mid;l++)
        	sorted[k++]=list[l];
    //(중요)배열 sorted[]의 리스트를 list[]로 복사
    for(l=left;l<=right;l++)
    	list[l]=sorted[l];
}

 

시간복잡도

 

1. 분할: O(1)

2. 합병: 입력의 크기에 비례

- 최소비교횟수: 작은 것의 크기만큼(n)

- 최대비교횟수: 정렬된 리스트의 데이터가 번갈아가면서 선택됨(m+n-1)

 

<층별 비교 횟수>

 

n을 계속하여 1/2로 나누다가, 더이상 나눌 수 없는 크기인 1이 될 때 분할 중단

k번 1/2로 분할했으면 -> k개의 층

2^k=n -> k=log2n

 

- 층 수=log2n

- 각 층에서 수행된 비교 횟수=O(n)

=> O(nlogn)

 

단점

 

- 변수, 인덱스 등을 위한 O(1) 크기의 메모리 공간 따로 필요

- O(n) 크기의 공간복잡도 필요

∵ 추가 공간이 필요하기 때문에 꼭 필요

sorted[]

 

응용

 

- 외부 정렬의 기준이 됨

- 연결리스트에 있는 데이터 정렬 시 퀵/힙 정렬보다 효율적

- 멀티코어 CPU와 다수의 프로세서로 구성된 그래픽 처리 장치의 등장으로 정렬 알고리즘을 병렬화하는 데 합병 정렬 알고리즘 활용