[Data Structure] 병합 정렬(merge sort)

---

병합 정렬

 

 

 

리스트를 균등하게 분할하고, 병합하면서 정렬하는 방법이다. 분할 정복 알고리즘의 대표적 예시 중 하나이다. 합병 정렬이라고도 한다.

정렬은 데이터를 크기가 1이 될때까지 분할하고 다시 병합하면서 일어난다. 병합할 때 분할된 왼쪽 부분 리스트와 오른쪽 부분 리스트의 첫번째 값부터 차례대로 읽으면서 작은 값을 임의의 리스트에 넣어 정렬하는 것이다. 그렇게 병합이 된다면, 다시 상위의 부분 리스트와 병합하여 정렬하고, 다시 상위의 부분 리스트와 병합하여 정렬하여 최종적으로 분할된 모든 리스트를 병합하면 정렬이 끝난다. 이때 분할에서 재귀가 사용된다.

새로운 리스트를 만들어서 병합 과정에서 사용하기 때문에 별도의 메모리 공간이 필요하고, 각 분할을 재귀로 구현해야하기 때문에 스택 메모리도 많이 사용한다는 단점이 있지만, 대상 리스트의 정렬 상태와 관계없이 $ \mathcal{O} (n \log_2 n)$의 시간복잡도를 가지고, 안정적인 정렬이라는 장점이 있다.

 

---

예시

 

예를 들어 위와 같은 리스트를 정렬한다고 해보자. 먼저 아래와 같이 분할을 해주어야 한다.

분할이 끝났다면 병합을 해주어야 한다. 크기가 2인 리스트에서의 병합은 크기를 비교한 후 교환하는 것과 같다. 

가장 작을 때 병합이 되었다면 그보다 상위에서 다시 병합을 한다.

병합을 할 때는 새로운 메모리 공간을 만들어 사용한다. 새로운 메모리 공간에 병합해야 하는 분할된 두 리스트의 앞쪽 값부터 읽으면서 작은 값을 넣는다.

모두 넣었다면 병합이 끝난 것이다. 이제 정렬된 리스트를 원래의 리스트에 복사한다.

이제 다시 아래와 같이 병합을 한다.

$$ \vdots $$

처음 나눈 두 분할의 병합이 끝났다면 반대편도 정렬한다.

$$ \vdots $$

$$ \vdots $$

병합이 끝났다면 다시 상위의 병합을 진행한다.

반씩 나누기 때문에 분할이 $ \mathcal{O} (\log_2 n) $ 의 시간복잡도를 가지고, 병합도 반대로 같은 방식으로 이뤄지기에 $ \mathcal{O} (\log_2 n) $ 의 시간복잡도를 가진다. 이때 모든 값을 비교해야 하므로 모든 레코드에 접근하고, 따라서 비교에서 $ \mathcal{O} (n) $ 의 시간복잡도(자세히는 $ \mathcal{O} (2n) $)를 가진다. 즉 전체적으로 $ \mathcal{O} (n \log_2 n) $ 의 시간복잡도를 가진다.

 

---

구현 | C

 

병합 부분을 따로 구현하였고, 임의의 리스트를 전역변수로 구현하였지만, 병합 부분을 정렬 함수 안에 넣을 수도 있고, 임의의 리스트를 동적 할당으로 구현할 수도 있다.

# define MAX_SIZE 100
int sorted[MAX_SIZE];

void merge(int list[], int left, int mid, int right) {
    int 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 (int l = j; l <= right; l++) {
            sorted[k++] = list[l];
        }
    }
    else {
        for (int l = i; l <= mid; l++) {
            sorted[k++] = list[l];
        }
    }
    for (int l = left; l <= right; l++) {
        list[l] = sorted[l];
    }
}

void merge_sort(int list[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        merge_sort(list, left, mid);
        merge_sort(list, mid+1, right);
        merge(list, left, mid, right);
    }
}