[Algorithm] 병합 정렬(Merge Sort)

병합 정렬

: 대표적인 분할 정복 방법을 채택한 알고리즘으로 O(NlogN)의 시간 복잡도를 가지는 정렬 알고리즘

 

특징

-. 일단 반으로 정확히 나누고 나중에 합치는 방식으로, 퀵 정렬(Quick Sort)와 다르게 Pivot 값이 존재하지 않는다.

-. 기존 데이터를 담을 추가적인 배열이 필요하다는 점에서 메모리 활용은 비효율적이다.

-. 초기 단계에는 모두 원소가 1인 상태로 분할되어있으며, 한 번 병합할 때마다 2의 배수만큼 씩 병합한다.

-. 너비는 N이지만 높이는 logN이기 때문에 전체 시간 복잡도는 NlogN이다.

너비? 높이?

너비: i와 j를 비교해 더 작은 값을 k 위치에 저장

        N번의 시도 후 정렬 완료

높이: 너비 정렬을 총 logN 번 반복하면 정렬 완료

 

병합 정렬(Merge Sort) Sequence

 

코드

#include <iostream>
using namespace std;
#define number 8

int sorted[8]; // 정렬된 배열. 반드시 전역 변수로 선언.

void merge(int a[], int m, int middle, int n){
    // m: 정렬할 배열의 시작 지점
    // middle: 정렬할 배열의 중간 지점
    // n: 정렬할 배열의 끝 지점

    int i = m;
    int j = middle+1;
    int k = m;

    // 작은 순서대로 배열에 삽입
    while(i<=middle && j <= n){
        // i가 j보다 더 작으면 새로운 배열에 저장
        if(a[i] <= a[j]){
            sorted[k] = a[i];
            i++;
        }
        // 그렇지 않으면 j 값 저장
        else{
            sorted[k] = a[j];
            j++;
        }
        k++; // 한 번 저장하면 k 증가
    }

    // 남은 데이터 삽입
    // i가 먼저 끝났다면 j 모두 새로운 배열에 저장
    if(i > middle){
        for(int t = j; t <= n; t++){
            sorted[k] = a[t];
            k++;
        }
    }
    // j가 먼저 끝났으면 i 모두 새로운 배열에 저장
    else{
        for(int t = i;t<=middle;t++){
            sorted[k] = a[t];
            k++;
        }
    }

    // 정렬된 배열을 실제 배열에 삽입
    for(int t = m; t <= n; t++){
        a[t] = sorted[t];
    }
}

void merge_sort(int a[], int m, int n){
    // 크기가 1보다 큰 경우 return
    if(m < n){
        int middle = (m+n) / 2;
        merge_sort(a, m, middle); // middle을 기준으로 왼쪽 병합정렬
        merge_sort(a, middle+1, n); // middle을 기준으로 오른쪽 병합정렬
        merge(a, m, middle, n); // 정렬 후 합치기
    }
}

int main(void){
    int arr[number] = {7, 6, 5, 8, 3, 5, 9, 1};
    merge_sort(arr, 0, number-1);
    for(int i=0;i<number;i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}

출력

1 3 5 5 6 7 8 9

 

시간 복잡도

병합정렬은 정확히 반씩 나눈다는 점에서 최악의 경우에도 NlogN을 보장한다.

☞ 퀵 정렬이 가지는 한계(Pivot 값에 따라 편향되게 분할할 가능성이 있다는 점에서 최악의 경우 O(N^2)의 시간 복잡도를 가짐)를 보완할 수 있음.