합병정렬(merge sort)

분할 정복(divide and conquer)

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

 

- 분할(Divde) 

입력 배열을 같은 크기의 2개의 부분 배열로 분할

- 정복(Conquer)

부분 배열을 정렬

- 결합(Combine) 

정렬된 부분 배열들을 하나의 배열에 합병

 

#include <stdio.h>
int sorted[8];

void merge(int list[], int left, int mid, int right){
    int i,j,k,l;
    i=left; //왼쪽 배열의 첫 인덱스
    j=mid+1; //오른쪽 배열의 첫 인덱스
    k=left; //임시 배열 인덱스

    // 합병
    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<=right; 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];
    }
}

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 main(){
    int i;
    int n=8;
    int list[8]={21,10,12,20,25,13,15,22};

    // left : 배열의 시작, right : 배열의 끝
    merge_sort(list, 0, n-1);

    for (i=0; i<n; i++){
        printf("%d\n",list[i]);
    }

    return 0;
}

 

 

참고

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog