[Algorithm] 병합 정렬(Merge Sort)

병합 정렬이란?

분할 정복 방법을 사용하는 정렬이다. 정확하게 반 씩 나누면서 정렬한다. 먼저 반으로 나눈 뒤, 나중에 합쳐서 정렬한다.

모든 요소가 자기 자신만 남을 때 까지 반으로 나눈다.

그 다음 인접한 두 수끼리 합친다.(각각 숫자 2개씩) 합치면서 두 수를 비교하여 정렬한다.

그 후 인접한 두 집합(각각 2 수를 가진 집합. 총 4개의 수를 가지게 됨)를 합치면서 정렬한다.

이런식으로 집합이 하나만 남을 때 까지 합치면서 정렬한다.

#include <stdio.h>
#include <iostream>
using namespace std;

int number = 8; // 정렬할 데이터의 수 
int sorted[8]; // 정렬 된 결과를 담을 곳  

void merge (int *data, int start, int middle, int end){ 
    int i = start; // 첫 번째 집합의 탐색 시작 점  
    int j = middle + 1; // 두 번째 집합의 탐색 시작 점 

    int k = start; // 정렬한 결과를 담을 배열의 index 

    // 작은 순서대로 배열에 삽입
    while(i <= middle && j <= end){
        // 첫 번째 배열의 요소가 두 번째 배열의 요소 값 보다 작다면
        if(data[i] <= data[j]){
           sorted[k] = data[i];
           i++;  
        } else {
            sorted[k] = data[j];
            j++;
        }
        k++;
    }
    // 남은 데이터 삽입(i 나 j의 모든 요소가 배열에 들어간 경우 나머지의 요소도 배열에 넣어줘야 함)
    // i 값이 모두 배열에 들어간 경우
    if(i > middle){
        for(int t=j;t<=end;t++){
            sorted[k] = data[t];
            k++;
        }
    } else { // j 값이 모두 배열에 들어간 경우 
        for(int t=i;t<=middle;t++){
            sorted[k] = data[t];
            k++;
        }
    }
    // 정렬된 배열을 삽입
    for(int t=start;t<=end;t++){
        data[t] = sorted[t];
    }

}

void mergeSort(int *data, int start, int end){

    // 크기가 1보다 큰 경우
    if(start < end){
        int middle = (start + end) / 2; // 시작과 끝을 더하여 반으로 나눠줌 
         mergeSort(data, start, middle); // 중앙을 기점으로 시작부터 중간까지 나누기 
         mergeSort(data, middle+1, end); // 중앙을 기점으로 중간부터 끝까지 나누기
         merge(data, start, middle, end); // 정렬된 2개의 배열을 나중에 합쳐줌 
    }
}

int main(void){
    int arr[] = {7, 6, 5, 8, 3, 5, 9, 1};

    mergeSort(arr, 0, number-1);

    for(int i=0;i<number;i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0; 
}

시간 복잡도

정렬해야 할 데이터가 N개라고 하면, 이 데이터의 배열을 다시 합치면서 정렬하는 과정은 로그의 밑이 2인 logN이다. 만약 데이터의 수가 8이면, 합치는 과정은 총 3번만 필요하므로, (log8 = 3) 이기 때문이다.

즉 시간복잡도는 O(N logN)이다. 무조건 반으로 나누기 때문에 퀵 정렬보다는 느리지만, 퀵 정렬과 달리 최악의 경우도 N logN을 보장해준다.

그러나 기존 데이터를 담을 추가 공간이 필요하므로 메모리 활용이 비효율적이다.

reference: https://www.youtube.com/watch?v=ctkuGoJPmAE&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=8