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

 

알고리즘

병합 정렬(Merge Sort)의 알고리즘은 다음과 같습니다.

 

[일단 반으로 나누고, 나중에 병합해 준다]

 

• 정렬할 배열을 모두 크기가 1인 개별 배열인 상태로 시작합니다.
• 크기가 1이었던 배열들을 크기가 2인 배열로 묶으면서 정렬을 수행합니다.
• 모두 합칠 때까지 반복합니다.

예를 들어 다음 배열을 정렬해보겠습니다.

[4 , 6 , 8 , 1 , 3 , 5 , 7 , 2 ]

1) 정렬할 배열은 모두 크기가 1인 개별 배열인 상태로 시작합니다.

[ 4 ]  [ 6 ]  [ 8 ]  [ 1 ]  [ 3 ]  [ 5 ]  [ 7 ]  [ 2 ]

2) 배열을 합치면서 정렬을 수행합니다.

[ 4 , 6 ]  [ 1 , 8 ]  [ 3 , 5 ]  [ 2 , 7 ]

 ↓

[ 1 , 4 , 6 , 8 ]  [ 2 , 3 , 5 , 7 ]

↓

[ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ]

 

---

시간 복잡도

병합 정렬의 시간 복잡도는 O(N x logN)입니다.

 

위의 예제를 예로 들어 왜 병합 정렬의 시간 복잡도가 O(N x logN)인지에 대해 설명하겠습니다.

 

위의 예제를 보면 8개의 원소가 있는 배열을 합치는 단계가 3단계밖에 필요하지 않았습니다.

 

즉, log8 = 3 이므로, 병합 하는 작업은 logN의 시간 복잡도를 가집니다.

 

병합하며 정렬하는 과정에서의 시간 복잡도는 N입니다. 즉, 데이터 개수만큼 연산하면 됩니다.

 

병합하는 작업이 logN의 시간 복잡도를 갖는 것은 대부분 이해할 수 있는데, 정렬하는 과정이 어떻게 O(N)일까 하시는 분들이 많을 수 있습니다. 저 또한 그랬습니다.

 

예를 들어 다음 두 배열들을 병합한다고 해보겠습니다.

[ 4 , 6 ]   [ 1 , 8 ]

그럼 [ 4 , 6 ] 배열의 첫 번째 원소에 i, [ 1, 8 ] 배열의 첫 번째 원소에 j를 부여하겠습니다.

병합 하기 전의 배열인 [ 4 , 6 ] 과 [ 1 , 8 ] 은 모두 이미 정렬 되어있다고 가정해 작은값 부터 차례대로 넣어주면 됩니다.

 

i와 j를 비교해가며 배열에 작은 값부터 채워 나가면 됩니다.

 

[ 4 , 6 ]   [ 1 , 8 ]     i = 4, j = 1

새로운 배열: [ ]

 

[ 4 , 6 ]   [ 1 , 8 ]     i = 4, j = 8

새로운 배열: [ 1 ]

 

[ 4 , 6 ]   [ 1 , 8 ]     i = 6, j = 8

새로운 배열: [ 1 , 4 ]

 

[ 4 , 6 ]   [ 1 , 8 ]     i = 6, j = 8

새로운 배열: [ 1 , 4 , 6 ]

 

[ 4 , 6 ]   [ 1 , 8 ]     i = 6, j = 8

새로운 배열: [ 1 , 4 , 6 , 8 ]

 

위의 과정을 보면 총 4번의 i와 j의 비교 연산이 진행됩니다.

즉 비교 연산을 N번만 처리하면 되는것이라 정렬이 O(N)입니다.

 

결과 적으로 병합 O(logN) x 정렬 O(N) = O(N X logN)입니다.

 

하지만 병합 정렬은 기존의 데이터를 담을 추가적인 배열이 필요하다는 메모리 활용이 비효율적이라는 단점이 있습니다.

 

병합 정렬은 퀵 정렬보단 느리지만 항상 O(N x logN)을 보장할 수 있다는 장점이 있습니다.

---

소스코드

위의 내용을 바탕으로 C++로 소스코드를 작성해 보겠습니다.

 

#include <bits/stdc++.h>
using namespace std;

//배열 원소의 갯수
int number = 8;
//정렬하고 담을 추가 배열
int sorted[8];

//병합 함수
void merge(int arr[], int m, int middle, int n) {
    //i 는 첫 번째 원소
    int i = m;
    //j 는 중간 바로 다음번째 원소
    int j = middle + 1;
    //K 는 첫 번째 원소
    int k = m;

    //i랑 j 비교해 작은 순서대로 k, 배열에 삽입
    //i는 중간 까지, j는 마지막 까지 도달할때 까지 반복
    while(i <= middle && j <= n) {
        if(arr[i] <= arr[j]) {
            sorted[k] = arr[i];
            i++;
        } else {
            sorted[k] = arr[j];
            j++;
        }
        k++;
    }
    //i 쪽의 원소를 모두 넣었다면 남은 j값들 넣어주기
    if(i > middle) {
        for(int t=j ; t<=n; t++) {
            sorted[k] = arr[t];
            k++;
        }
    } //j 쪽의 원소를 모두 넣었다면 남은 i 값들 넣어주기
    else {
        for(int t=i; t<=middle ;t++) {
            sorted[k] = arr[t];
            k++;
        }
    }
    //정렬된 배열을 삽입
    for(int t=m;t<=n;t++)
        arr[t] = sorted[t];
}

//병합 정렬 함수
void mergeSort(int arr[], int m, int n){
    //원소가 1개 보다 많을 때만!
    if(m<n) {
        int middle = (m+n)/2;
        //배열을 절반으로 나누고
        mergeSort(arr, m, middle);
        mergeSort(arr, middle+1, n);
        //나중에 합친다
        merge(arr , m , middle, n);
    }
}

int main(void){
    int array[number] = {4,6,1,8,3,5,7,2};
    mergeSort(array, 0, number-1);

    for(int i=0;i<number;i++)
        cout << array[i] <<" ";
}

 

위 코드를 실행시켜 보면 다음과 같이 정렬된 배열을 확인할 수 있습니다.