[Algorithm] Sort #4 - 병합 정렬 Merge Sort

병합 정렬이란?

 리스트를 분할하고 다시 역순으로 병합하면서 정렬하는 알고리즘

 

시간 복잡도

최상 : \( O(n \log n) \)

최악 : \( O(n \log n) \)

 

관련 글

[Algorithm] Sort #1 - 버블 정렬 Bubble Sort

[Algorithm] Sort #2 - 선택 정렬 Selection Sort

[Algorithm] Sort #3 - 삽입 정렬 Insertion Sort

[Algorithm] Sort #5 - 힙 정렬 Heap Sort

[Algorithm] Sort #6 - 퀵 정렬 Quick Sort

 

---

 

 이전 글에서 소개한 버블 정렬, 선택 정렬, 삽입 정렬은 모두 평균 시간 복잡도가 \( O(n^2) \)인 알고리즘들입니다. 이제부터 소개해드릴 정렬 알고리즘들은 \( O(n \log n) \)으로써 더 빠른 성능을 보여줍니다. 그중에서 첫 번째로는 병합 정렬입니다.  

 

알고리즘

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

1. 리스트를 1개의 원소들만 남을 때까지 계속 절반으로 분할한다.
2. 분할시킨 원소들을 1의 과정의 역순으로 병합 정렬한다.
3. 하나의 리스트로 병합될 때까지 수행한다.

 

병합 정렬 예시

 { 9, 1, 7, 5, 2} 순서대로 원소가 존재한다고 가정했을 때 병합 정렬의 예시는 다음과 같습니다. 이때 원소의 수가 홀수일 경우에는 분할 과정이 남았지만 더 이상 분할할 수 없는 그룹이 존재하게 됩니다. 이 때는 모든 분할 과정이 끝날 때까지 계속 1개의 원소를 유지합니다.

 

 분할 과정이 모두 끝났다면 다시 역순으로 정렬함과 동시에 병합 과정을 진행합니다. 그래서 병합 과정이 모두 끝난 시점에는 모든 원소가 정렬되어 있는 것을 확인할 수 있습니다.

 

 

 

 병합하는 과정에서 정렬하는 방법은 아래와 같습니다. 이 알고리즘의 특징으로는 병합되는 그룹은 이미 정렬이 되어 있다는 것입니다 (원소 1개도 정렬되어 있다고 취급). 그래서 병합되기 전 left, right 그룹의 원소를 비교하여, 작은 수를 병합 그룹에 순차적으로 위치시키면 됩니다.

 

 

시간 복잡도 계산

 병합 정렬의 시간복잡도는 최악, 최상의 경우가 같고 분할, 병합 과정으로 나누어 생각할 수 있습니다.

 

 

분할

 분할 과정은 원소의 개수가 \( n = 2^k \)개일 때 지속적으로 이분화되어 깊이는 \( log n = log 2^k = k \) 입니다. 그래서 시간 복잡도는 \( O(\log n) \)으로 표현할 수 있습니다.

 

병합

 병합 과정의 경우 똑같이 \( \log n = k \) 깊이를 가지고 병합이 되는 깊이마다 \( n \)번 만큼 정렬 과정을 수행합니다. 왜냐하면 분할을 할수록 깊이에 따라 그룹은 2배 증가하고 그룹이 가지는 원소의 수는 2배 줄어들기 때문입니다. 그러므로 (정렬 횟수 x 깊이)를 n으로 표현하면 \( n \) x \( \log n \)이고 결국 \( O( n \log n) \)입니다.

 

 그래서 최종적으로 분할 과정과 병합 과정을 모두 생각한다면 \( O( \log n) + O(n \log n) \) 이므로 \( O( n \log n) \)입니다.

 

 이전 글에서 설명한 버블 정렬, 선택 정렬, 삽입 정렬보다 병합 정렬이 상당히 빠르다고 볼 수 있습니다.

C++ Code

#include <iostream>
#include <vector>

using namespace std;

vector<int> arr = {9,1,7,5,2};

vector<int> two_arr_sort(vector<int> f, vector<int> s){
    int f_p = 0, s_p = 0;
    
    vector<int> temp;
    
    while(!(f_p >= f.size() && s_p >= s.size())){
        if( (f_p < f.size() && f[f_p] <= s[s_p]) || s_p >= s.size() ){
            temp.push_back(f[f_p]);
            f_p++;
        }
        else{
            temp.push_back(s[s_p]);
            s_p++;
        }
    }
    
    return temp;
}

vector<int> merge_sort(int l, int r){
    if(l==r){
        vector<int> temp = {arr[l]};
        return temp;
    }
    
    int m = (l + r)/2;
    
    vector<int> first = merge_sort(l,m);
    vector<int> second = merge_sort(m+1,r);
    
    return two_arr_sort(first, second);
}

int main()
{
    arr = merge_sort(0, arr.size()-1);
    
    for(int i=0; i<arr.size(); i++)
        cout << arr[i];
}