병합 정렬(MergeSort)

목표

병합 정렬 정의 설명

과정 설명

구현

시간복잡도와 공간복잡도 계산

정의

병합 정렬은 비교 기반 정렬 알고리즘으로 분할 정복 알고리즘의 하나이다. 일반적인 기법을 사용하면 안정 정렬이다.

과정설명

1. 리스트의 길이가 0과 1은 이미 정렬되어 있는 경우이며 그 외의 경우에는

2. 리스트를 절반으로 쪼갠다.

3. 나누어진 리스트를 정렬한다.

4. 두 리스트를 하나의 리스트로 병합한다.

구현

#include <iostream>
using namespace std;
int arr[1000000], temp[1000000];


void sort(int start, int middle, int end) // 정렬
{
    int a = start, b = middle+1, num = start;
    while(a<= middle && b <= end) // 두 리스트 비교하며
    {
        if(arr[a] < arr[b])
            temp[num++] = arr[a++];
        else
            temp[num++] = arr[b++];
    }
    if(a > middle) // a 리스트를 모두 사용한 경우
    {
        while(b <= end)
            temp[num++] = arr[b++];
    }
    else // b 리스트를 모두 사용한 경우
    {
        while(a <= middle)
            temp[num++] = arr[a++];
    }
    for(int i = start; i<=end; i++) // temp배열을 arr에 복사
        arr[i] = temp[i];
}
void merge(int start, int end) // 정렬하기 위해 분할
{
    if(start == end || start > end)
        return;
    int middle = (start+end)/2;
    merge(start, middle);
    merge(middle+1, end);
    sort(start, middle, end);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> arr[i];
    merge(0, n-1);
    for(int i=0; i<n; i++)
        cout << arr[i] << '\n';
    return 0;
}

시간복잡도와 공간복잡도의 계산

 

시간복잡도의 경우

다들 자연스럽게 nlogn으로 외우는데 그것에 대해 간략하게 정리해볼 것이다.

 

먼저 크기가 8인 리스트가 있다면 반의 분할을 총 3번 진행하여야 한다.

그 이유는 1번 분할 시 4 크기의 리스트가 2개 생기며, 여기서 또 분할 시 2 크기의 리스트가 4개 생기며, 한 번 더 분할 할시 1 크기의 리스트가 8개 생긴다.

즉 8 크기의 리스트 1개를 3번 분할 시 1 크기의 리스트가 8개 생성된다.

결국 분할한 뒤 합치는 과정을 n번 수행 시 8 크기의 리스트가 생성되는 것이다.

2^n = 8 이므로 n은 3이 된다. 

 

결국 이것을 식으로 만들면 먼저 2를 log8을 곱하면 3이 된다.

그 이유는 log의 성절 때문인데, 2^logn8= 3log2 = 3이므로  밑이 2인 로그이므로 3이 된다.

결국 8이 아니라 n으로 일반화된다면

2^logn = nlog2 = n 이므로 2를 총 logn번 곱하면 n이 된다.

 

분할 과정에서 logn이고 합병과 정렬 과정에서 결국 모든 레벨에서 정렬을 위해 n개의 배열에 모두 접근하기에   n * logn이 되기에

시간 복잡도는 O(nlogn) 이다.

 

 

공간 복잡도의 경우

정렬을 위해 복사 배열을 요구한다. 그렇기에 공간적으로는 비효율적인 배열이라고 할 수 있다.

O(n)

 

 

공간적 비효율때문에 퀵 정렬이 더 좋을 것 같지만 병합 정렬의 경우 최선, 평균, 최악 모두 O(nlogn)으로 동일하므로 최악의 경우에 퀵 정렬은 매우 느리기에 공간이 충분하다면 병합 정렬을 사용하는 것이 좋다.