[알고리즘] 병합정렬(Merge Sort) -C/C++

<병합정렬(Merge Sort)> 

- 부분집합으로 분할(Divide)하고 분할된 각 부분집합을 병합(Merge)하면서 정렬하는 분할정복(Divde&Conquer) 기법의 정렬 알고리즘

<시간복잡도>

* 최선, 평균, 최악 :

- 상당히 효율적인 정렬 알고리즘임을 알 수 있다.

- 단 추가 메모리 공간이 필요하기 때문에 배열의 크기가 큰 경우는 비효율적이다.

 

<mergeSort>

void mergeSort(int arr[], int buffer[], int start, int end) {
    if(start < end) {
        int middle = (start + end) / 2;
        mergeSort(arr, buffer, start, middle);
        mergeSort(arr, buffer, middle + 1, end);
       // divde
        
        int i = start;
        int j = middle + 1;
        int k = start;
        
        while(i <= middle || j <= end ) {
            if(arr[i] < arr[j] || j > end)
                buffer[k++] = arr[i++];
            else
                buffer[k++] = arr[j++];
        }
        
        for(int l=start; l<=end; ++l)
            arr[l] = buffer[l];
       // merge
    }
}

- 2~5줄까지 분할(Divide) 작업 / 8~21줄까지 병합(Merge) 작업

 

<main>

#define SIZE 8

void printAll(int arr[], int size){
    for(int i = 0; i < size; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
    return;
}

int main(int argc, const char * argv[]) {
    int arr[SIZE] = {80, 50, 70, 10, 60, 20, 40, 30};
    int buffer[SIZE];
    
    printf("before : ");
    printAll(arr, SIZE);
    
    mergeSort(arr, buffer, 0, SIZE - 1);

    printf("after : ");
    printAll(arr, SIZE);
    
    return 0;
}

 

<결과>