[Algorithm] 합병 정렬 (Merge Sort)

Merge Sort

• 분할 정복 알고리즘을 사용한 정렬
• 위치에 따른 균등 분할
• 모든 원소를 하나가 될 때까지 나눈 후, 순서를 맞춰 다시 합침

코드

#include <iostream>

int temp[100];

void Print(int* arr)
{
    for (int i = 0; i < 10; i++)
    {
        std::cout << arr[i] << " ";
    }
    std::cout << "\n";
}

void Merge(int* arr, int p, int q, int r)
{
    int i = p; // 왼쪽 부분 배열 포인터
    int j = q+1; // 오른쪽 부분 배열 포인터
    int k = p; // temp 배열 포인터

    // 부분 배열의 두 부분에서 작은 값부터 차례대로 임시 배열에 복사
    while (i <= q && j <= r)
    {
        if (arr[i] > arr[j])
            temp[k++] = arr[j++];
        else
            temp[k++] = arr[i++];
    }

    // 남은 값 모두 옮기기
    while (i <= q)
        temp[k++] = arr[i++];
    while (j <= r)
        temp[k++] = arr[j++];

    // 원본 배열로 복사
    for (int i = p; i <= r; i++)
        arr[i] = temp[i];
}

void MergeSort(int* arr, int p, int r)
{
    if (p < r)
    {
        int q = (p + r) / 2;
        MergeSort(arr, p, q);
        MergeSort(arr, q+1, r);
        Merge(arr, p, q, r);
    }
}

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

    int arr[10] = {8, 31, 48, 73, 3, 65, 20, 29, 11, 15};

    Print(arr);
    MergeSort(arr, 0, 9); // O(nlogn)
    Print(arr);
}

MergeSort 함수에서 p와 r은 배열의 처음과 마지막을 가리키는 포인터다. p < r인 동안은 부분 배열의 크기가 2 이상인 것이므로 그 둘의 중간 q를 구한 후, 부분 배열 앞쪽 p ~ q, 뒤쪽 q+1 ~ r로 나눈다. 부분 배열의 크기가 1이 될 때까지 반복한다.

 

Merge 함수에서는 나뉜 배열의 arr[p ~ q]와 arr[q+1 ~ r]을 정렬해서 합친 새로운 배열 temp를 만든다. 모든 과정이 끝났다면 원본 배열로 복사한다.

Merge 함수는 해당 구조를 생각하면 쉽게 이해할 수 있다. i와 j가 가리키는 배열은 p, q, r로 구분된 arr이고, k가 가리키는 배열은 temp 배열

시간 복잡도

O(nlogn)으로 효율적인 알고리즘임.

참고사항

• 나누는 역할을 하는 MergeSort 함수와 나누어진 부분 배열을 정렬해 하나로 합치는 Merge 함수의 역할과 순서를 명확히 알자.