[Algorithm] 합병정렬 (Merge Sort) C++

1. 합병정렬 정의

분할 정복 알고리즘의 하나로, 더 이상 쪼개지지 않을때까지 작은 크기로 분할하여, 작은 배열끼리 비교하는 과정을 수행해 하나의 배열로 합치는 정렬이다.

 

• 과정
• 1. 원래 배열을 두 개의 작은 배열로 분할하여 더 이상 쪼개지지 않을 때까지 재귀적으로 수행한다.
• 2. 가장 작은 크기의 배열부터 시작하여, 두 개의 배열을 서로 비교하면서 오름차순(또는 내림차순)으로 정렬해 합친다.

 

• 합병정렬 예제

1단계 - 분할 , 2단계 - 합병

 

2. 합병정렬 특징

- 장점

안정적인 정렬 방법 (입력한 값이 무엇이든 간에 정렬되는 시간은 O(nlog2n)으로 동일하다)

 

- 단점

배열 크기가 큰 경우에는 이동횟수가 많아 시간적 측면에서 크게 낭비된다.

 

3. 시간 복잡도

- Best Case

O(nlog2n)

 

- Worst Case

O(nlog2n)

 

4. 구현 방법 (C++)

int arr[100];
int sorted[100];

void merge(int start, int end){
    int mid = (start + end) / 2;
    int i = start, j = mid+1, k = start;
    while (i <= mid && j <= end) {
        if (arr[i] <= arr[j]) 
            sorted[k++] = arr[i++];
        else
            sorted[k++] = arr[j++];
    }
    while (i <= mid)
        sorted[k++] = arr[i++];
    while (j <= end)
        sorted[k++] = arr[j++];
 
    for (int i = start; i <= end; i++) {
        arr[i] = sorted[i];
    }
}

void merge_sort(int start, int end) {
    if (start < end) {
        int mid = (start + end) / 2;
        merge_sort(start, mid);
        merge_sort(mid + 1, end);
        merge(start, end);
    }
}