[자료구조] Merge Sort(병합 정렬)

오늘은 Merge Sort에 대해 다뤄보도록 하겠습니다. 정렬 자료구조는 어느 파트에서나 정말 많이 쓰고 정말 중요한 자료구조인 것 같아요. 알고리즘 과정과 c++ 코드 구현, 시간 복잡도 등의 내용을 담아 설명해보도록 하겠습니다.

1. Merge Sort 설명

1. 리스트를 두 개로 분할
2. 리스트를 각각 정렬
3. 두 리스트를 합친다

Merge Sort는 위와 같은 과정으로 정렬이 이루어집니다. 그러면 우리는 이제 어떻게 한 리스트를 두 개로 분할하는지, 어떻게 각 리스트를 정렬하는지, 어떻게 두 리스트를 합치는 지를 알아보면 됩니다. 먼저 합치는 것부터 알아보도록 하겠습니다.

정렬된 두 배열 합치기 (투포인터)

배열 a와 b는 정렬된 상태로 들어온다고 가정한다.

주의할 점 : Merge Sort는 stable sort이므로 중복된 숫자 있을 때 순서 유지해야한다. 그래서 a[ai] <= b[bi] 이렇게 등호를 넣어야한다. stable sort에 대해서는 마지막에 다루도록 하겠다.

#include <iostream>
#include <algorithm>
using namespace std;

int N, M;
int a[1000002];
int b[1000002];
int ans[1000002];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for (int i=0; i<N; i++) cin >> a[i];
    for (int i=0; i<M; i++) cin >> b[i];

    int ai = 0;
    int bi = 0;
    int i=0;
    for (i=0; i<N+M; i++){
        if (ai == N) ans[i] = b[bi++];
        else if (bi == M) ans[i] = a[ai++];
        else if (a[ai] <= b[bi])
            ans[i] = a[ai++];
        else
            ans[i] = b[bi++];
    }
    
    
    for (int i=0; i<N+M; i++) cout << ans[i] <<' ';

    return 0;
}

이제 정렬된 두 배열을 합칠 수 있게 되었다. 이것이 정복 과정이다! (이 과정에서 임시 배열, 즉 추가 공간을 O(N)필요로 한다.) 그러면 만약 a와 b가 정렬이 안되어있을 경우에는 어떻게 해야할까? 바로 재귀를 사용한다.

재귀

도미노 예시를 들어보자. 1부터 100까지 도미노가 일렬로 서있다고 하자. 1번 도미노가 쓰러지면 100번 도미노도 쓰러진다. 이를 수학적 귀납법을 사용하여 증명해보자.

1) 1번 도미노가 쓰러진다. 2) k번 도미노가 쓰러지면, k+1 도미노도 쓰러진다.

100번 도미노가 쓰러지기 위해선 99번 도미노가 쓰러져야 하고, 99번 도미노가 쓰러지기 위해서 98번 도미노가 쓰러져야한다. 쭉 이어서 해보면 2번 도미노가 쓰러지기 위해선 1번 도미노가 쓰러져야한다. 그런데 첫 조건이 ‘1번 도미노가 쓰러진다’ 이기 때문에 위 수식을 증명하게 된다.

정렬

위 도미노의 예시처럼 수학적 재귀법을 사용해 리스트 정렬 방법을 생각 해보자.

1) 길이가 1인 리스트를 정렬할 수 있다. 2) 길이가 k인 리스트를 정렬할 수 있으면, 길이가 k+1인 리스트도 정렬할 수 있다.

따라서 재귀를 사용해 길이가 1인 리스트를 만들고, 병합하면서 정렬하는 과정을 거치면 된다!

2. 시간복잡도

이제 시간 복잡도에 대해 생각해보자. N = 2^k 인 길이를 가진 배열이 있다고 해보자.

분할

먼저 분할할 때 시간복잡도에 대해 알아보자. 길이가 1인 배열로 만들기 위해서 2^(k-1), 2^(k-2), … 1 까지 가야한다. 각 레벨에서 분할을 위한 함수 호출 횟수는 1, 2, 2^2, …, 2^(k-1), 2^k일 것이다(보다 쉬운 풀이를 위해 길이가 1일때도 함수 호출을 한다고 하자). 따라서 시간 복잡도는 함수 호출 횟수를 다 더하면 된다. 1+2+2^2+ … + 2^(k-1) + 2^k = 1*(2^(k+1) - 1) = 2N-1이므로 분할할 때 시간복잡도는 O(N)이 된다.

합병

정복할 때 위에서 한 것처럼 투포인터를 사용해 정렬을 하게 된다. 따라서 모든 레벨에서 N번의 연산이 필요하다. 레벨의 개수는 k개이므로 레벨의 개수는 logN(k = logN)이 된다. 따라서 시간복잡도는 O(NlogN)이다.

O(N)보다 O(NlogN)이 더 크므로 최종적으로 Merge Sort의 시간복잡도는 O(NlogN) 이다.

3. Merge Sort 코드 (c++)

#include <iostream>
using namespace std;

int n=10;
int arr[1000001] = {15, 25, 22, 357, 16, 23, -53, 12, 46, 3};
int tmp[1000001];

// 정렬된 배열 합치기
void merge(int st, int en){
    int mid = (st+en)/2;
    
    int idx1 = st;
    int idx2 = mid;
    for (int i = st; i<en; i++){
        if (idx1 == mid) tmp[i] = arr[idx2++];
        else if (idx2 == en) tmp[i] = arr[idx1++];
        else if (arr[idx1] <= arr[idx2]) tmp[i] = arr[idx1++];
        else tmp[i] = arr[idx2++];
    }

    for (int i=st; i<en; i++) arr[i] = tmp[i];
}

// 분할 & 정렬
void merge_sort(int st, int en){
    if (st+1 == en) return; // 길이가 1
    int mid = (st+en)/2;
    merge_sort(st, mid); 
    merge_sort(mid, en); 
    merge(st, en); // arr[st:md]와 arr[mid:st]를 병합
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    merge_sort(0, n);
    for (int i=0; i<n; i++) cout << arr[i] << ' ';

    return 0;
}

Stable Sort

우선순위가 같은 원소가 여러 개일 땐 정렬한 결과가 유일하지 않을 수 있다.

우선순위가 같은 원소들끼리는 원래의 순서를 따라가도록 하는 것이 Stable Sort다.

Stable Sort의 응용

시간순으로 오름차순으로 정렬된 파일을 크기순으로 변경하고 싶다. 이때 크기가 같다면 시간순을 따른다. 이때 merge sort를 이용해 크기순으로 정렬하면, 기존의 시간순을 유지한채 크기순으로 정렬되므로 원하는 결과를 얻을 수 있다.

4. 정리

1. Merge Sort는 두 개로 분할하고 정복(정렬, 병합)하는 과정으로 이루어진다. 정복과정에서 재귀를 사용한다.
2. Merge Sort는 Stable Sort이다.
3. Merge Sort의 시간복잡도는 항상 O(NlogN)이다
4. Merge Sort는 추가 공간으로 O(N)을 필요로 한다.

이렇게 Merge Sort를 정리해보았습니다! 다음번에는 Merge Sort와 동일하게 분할 정복을 사용하며 평균 시간복잡도 O(NlogN)을 갖는 Quick Sort(퀵소트)에 대해 다뤄보도록 하겠습니다. 끝까지 봐주셔서 감사합니다🙂

---

위 글은 [바킹독의 실전 알고리즘] 강의를 참고해 작성한 글입니다.
참고자료