[알고리즘] 합병 정렬 (분할정복 활용)

특정 리스트를 정렬하는 방법에는 여러 가지가 있다.

그중에서도 대표적으로 분할 정복을 활용하여 리스트를 정렬하는 것이 합병 정렬, 퀵 정렬이다.

그 중 합병 정렬에 대해 알아보자. 합병 정렬은 병합 정렬이라고도 불린다.

정렬된 두 리스트의 합 정렬

먼저 알아야 할 것이 있다. 합병 정렬은 정렬된 임의의 두 리스트가 있을 때, 두 리스트를 합치면서 정렬하기 위해서는 두 리스트의 성분을 처음부터 하나씩 비교해면서 새로운 리스트에 넣어주다가 둘 중 어느 한 리스트의 성분 모두 없어지면, 나머지는 그냥 새로운 리스트의 뒤에 들어가면 된다.

ex. [1,2,3,5] [4,6,7,8]이 있을 때 이를 합치면서 정렬하려 한다. 처음부터 성분을 비교하면서 넣다 보면 어느 순간 새로운 리스트에 [1,2,3,4,5]까지 들어가고 두 리스트가 [] [6,7,8] 상태가 될 것이다. 이때 남은 리스트에 있는 6,7,8 성분은 그냥 새로운 리스트 [1,2,3,4,5] 뒤에 붙여 [1,2,3,4,5,6,7,8]를 만들어주면 된다.

이러한 정렬된 임의의 두 리스트를 합칠 때의 과정에서 분할 정복의 개념을 더해 착안해 낸 것이 합병 정렬이다.

합병 정렬의 과정

리스트를 먼저 나눈다.(divide) 그리고 각각의 문제를 해결해야 하는데 여기서는 분할 정복을 반복해서 활용해야 하므로 리스트의 길이가 1이 될 때까지 문제를 나눠준다.(conquer) 리스트의 길이가 1일 경우 각각의 나눈 리스트를 더한다.(combine) 리스트를 더할 때는 위에서 본 '정렬된 두 리스트의 합 정렬'과정으로 더한다. combine 되는 리스트는 그 길이가 1일지라도 최소한 정렬된 알고리즘이기 때문에 정상적으로 정렬될 수 있다.

cf. 분할 정복의 3단계는 divide, conquer, combine이라고 했다. 하지만 이 셋만큼이나 중요한 것이 또 하나 있는데, 바로 base-case의 설정이다. base-case를 제대로 설정해주지 않으면 재귀를 활용한 분할 정복이 제대로 이뤄지지 않을 것이다. 위에서는 리스트의 길이가 1이 되었을 때가 base-case이다.

합병 정렬 구현 (by. C++)

#include <stdio.h>
int number = 8;

int size;
int sorted[8]; // 정렬할 때 사용할 배열, 해당 배열은 반드시 전역 변수로 선언 
int count = 0;

void merge(int a[], int m, int middle, int n) {
    int i = m;
    int j = middle + 1;
    int k = m;
    // 작은 순서대로 배열에 삽입 
    while(i <= middle && j <= n) {
        if(a[i] <= a[j]) {
            sorted[k] = a[i];
            i++;
        } else {
            sorted[k] = a[j];
            j++;
        }
        k++;
    }
    // 남은 데이터 삽입 
    if(i > middle) {
        for(int t = j; t <= n; t++) {
            sorted[k] = a[t];
            k++;
        }
    } 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 mergeSort(int a[], int m, int n) {
    // 이외의 경우는 크기가 1개인 경우 
    if(m < n) {
        int middle = (m + n) / 2;
        mergeSort(a, m, middle);
        mergeSort(a, middle + 1, n);
        merge(a, m, middle, n);
    }
}

int main(void) {
    int array[number] = {7, 6, 5, 8, 3, 5, 9, 1};
    mergeSort(array, 0, number - 1);
    for(int i = 0; i < number; i++) {
        printf("%d ", array[i]);
    }
} 

합병 정렬 구현 (by. python)

def combine(num_list, start_idx, mid_idx, end_idx):
    l_idx = start_idx # start_idx ~ mid_idx
    r_idx = mid_idx+1 # mid_idx+1 ~ end_idx

    sorted_list = []

    while l_idx <= mid_idx and r_idx <= end_idx:
        # if l_idx > mid_idx:
        #     # sorted_list.append(num_list[r_idx])
        #     # r_idx += 1
        #     sorted_list += num_list[r_idx:end_idx+1]
        #     r_idx = end_idx + 1
        # elif r_idx > end_idx:
        #     # sorted_list.append(num_list[l_idx])
        #     # l_idx += 1
        #     sorted_list += num_list[l_idx:mid_idx+1]
        #     l_idx = mid_idx + 1
        if num_list[l_idx] < num_list[r_idx]:
            sorted_list.append(num_list[l_idx])
            l_idx += 1
        else:
            sorted_list.append(num_list[r_idx])
            r_idx += 1

    sorted_list += num_list[r_idx:end_idx+1]
    sorted_list += num_list[l_idx:mid_idx+1]

    num_list[start_idx:end_idx+1] = sorted_list

def bottom_up_merge_sort(num_list):
    size = 1

    while size < len(num_list):
        start_idx = 0

        while start_idx < len(num_list):
            end_idx = min(start_idx + size * 2 - 1, len(num_list)-1)
            mid_idx = min(start_idx + size - 1, end_idx)

            combine(num_list, start_idx, mid_idx, end_idx)
            print(num_list)

            start_idx = end_idx + 1

        size *= 2

n = int(input())
num_list = []

for _ in range(n):
    num_list.append(int(input()))

bottom_up_merge_sort(num_list)

---

합병 정렬 과정 이미지

이미지 출처 : 위키백과 ( https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC )