[알고리즘] 1_4. 병합 정렬(Merge Sort)

1. 정의

병합정렬(Merge Sort)는 Divide and Conquer(분할정복) 알고리즘으로 분류되며, 일반적이고 간단한 방법으로 최대, 최악의 경우에도 O(nlogn)의 속도로 sort가 가능하다. Divide and Conquer로 제안된 Merge Sort 알고리즘은 Top-down 방식으로 구현되었다.(후에 Bottom-up 방식의 알고리즘도 발표되었다.) 정렬 방식은 전체의 원소를 1개 원소의 단위로 분할한 뒤, 다시 병합과정을 거쳐 새롭게 정렬된 배열을 생성한다. 같은 평균 속도 O(nlogn)를 가지는 Quick Sort, Heap Sort와 함께 실제로 사용한 경우, 비교적 느리다.(Quick>Heap>Merge 순서) Array의 정렬보다는 Linked List의 정렬에 주로 사용된다.(Array의 경우 추가공간 O(n)이, List의 경우 추가공간 O(1)이 필요하기 떄문.)

2. 설명

STEP 1. Divide(분할)

Divide and Conquer 문제를 풀듯이, 큰 문제를 작은 문제로 쪼개어 생각한다. Merge Sort에서는 정렬을 하고자 하는 큰 배열을 작게 나누어 생각한다. 쉬운 방법으로 하나의 배열을 원소 1개가 될때까지 반으로 쪼갠다.

STEP 2. Conquer(정복)

Merge Sort의 경우에는, Conquer 단계에서 별 다른 일을 수행하지 않는다.(Merge 과정을 통해서 정렬을 수행하기 떄문에, 사실상 Merge단계가 Conquer역할을 한다.)

STEP 3. Merge(병합)

STEP 1에서 쪼갠 배열의 각 원소를 다시 하나의 배열로 합쳐야한다. 이를 위해서 가장 아래(1개짜리 원소)부터 병합을 수행하는데, 두 개의 작은 배열을 합쳐 하나의 배열로 만들어나간다. Merge Sort는 이 병합과정에서 정렬을 한다. 병합하고자 하는 두 원소(쪼개어진 배열)의 각 원소를 비교해서 순서대로 하나의 결과배열에 저장한다. 이 과정을 반복해 정렬된 배열을 결과로 얻을 수 있다.

3. 코드

#include<stdio.h>
#include<stdlib.h>
 
void merge(int len1,int len2,int *data_front,int *data_back,int *data){
    int i,j,k;
    int *result=(int*)malloc(sizeof(int)*(len1+len2));
 
    k=0;
    for(i=0,j=0;i<len1&&j<len2;){
        if(data_front[i]<data_back[j])
            result[k++]=data_front[i++];
        else
            result[k++]=data_back[j++];
    }
    if(i==len1){
        while(j<len2) result[k++]=data_back[j++];
    }    
    else if(j==len2){
        while(i<len1) result[k++]=data_front[i++];
    }
    
    for(i=0;i<len1+len2;i++){
        data[i]=result[i];
    }
 
    free(result);
}
 
void merge_sort(int n,int *data){
    
    if(n==1) return;
 
    int len1,len2;
    int *data_front,*data_back;
 
    //reculsive(split)
    len1=n/2;len2=n-n/2;
    data_front=data;
    data_back=data+len1;
    merge_sort(len1,data_front);
    merge_sort(len2,data_back);
 
    //merge
    merge(len1,len2,data_front,data_back,data);
}
 
int main(void){
    int i,data[8]={10,2,3,9,8,5,7,6};
    
    merge_sort(8,data);
 
    for(i=0;i<8;i++){
        printf("%d ",data[i]);
    }
 
    return 0;
}