합병 정렬(Merge sort)

합병 정렬(Merge sort)이란?

• 합병정렬(merge sort)은 정렬 알고리즘의 한 종류로, 폰 노이만이 개발한 알고리즘이다.
• 이 정렬은 안정 정렬에 속하며, 분할 정복(divide and conquer) 알고리즘의 하나이다.

 

합병 정렬(Merge sort) 아이디어

https://en.wikipedia.org/wiki/Merge_sort

합병(Merge)라는 이름에서 알 수 있듯, 합병 정렬의 기본 아이디어는 정렬할 배열을 분할하여, 작은 조각으로 나눈 후 더 이상 나눌 수 없을 때(하나의 원소만 있을때) 다른 조각과 비교하며 합쳐 정렬하는 알고리즘이다.

과정

1.  정렬되지 않은 리스트를 2개의 리스트로 나눈다.
   
   • 각 리스트의 길이가 1이 될때까지 반복한다(길이가 1인 리스트는 정렬된 것으로 간주한다.)
2. 2개의 리스트의 값들을 처음부터 하나씩 비교하여 두 개의 리스트의 값 중에서 더 작은 값을 새로운 리스트로 옮긴다.
   • 둘중 한 리스트가 끝날 때까지 이를 반복한다.
   • 한 리스트가 끝나면, 나머지 값들은 새 리스트에 복사해서 넣어준다(이미 정렬되어 있으므로)
3. 2번 과정을 하나의 리스트가 될때까지 반복한다

 

합병 정렬(Merge sort) 증명

Merge 과정은 문제없이 기능한다 가정

귀납적 증명(Proof by Induction)

1. Base Case (기본 단계):

배열의 크기가 1 또는 0인 경우

• 배열의 크기가 0 또는 1이면, 이미 정렬된 상태이다.

---

2. Inductive Hypothesis (귀납 가정):

배열의 크기가 n 이하인 모든 배열에 대해 Merge sort가 올바르게 작동한다고 가정.

---

3. Inductive Step (귀납적 단계):

배열의 크기가 n+1인 배열에 대해서 Merge sort가 올바르게 작동함을 증명.

• 크기가 n+1인 배열 A를 반으로 나누어 두 개의 하위 배열 L과 R로 나눈다고 가정하자. 각 하위 배열의 크기는 대략 n/2 또는 그와 비슷하다.
• 귀납 가정에 따라, 배열 L과 배열 R에 대해 각각 Merge sort를 호출하면, L과 R은 각각 오름차순으로 정렬된다.
• Merge 과정이 끝나면, L과 R의 모든 요소가 오름차순으로 정렬된 하나의 배열로 합쳐지고. 이 배열은 오름차순으로 정렬된 상태이다.

따라서 배열의 크기가 n+1일 때도 Merge sort는 올바르게 작동한다.

 

합병 정렬(Merge sort) 시간복잡도

$T(n)=2T(\frac{n}{2})+n$ (이때 n은 merge시 걸리는 시간)

$\ \ \ \ \ \ \ \ =2(2T(\frac{n}{4})+\frac{n}{2})+n=4T(\frac{n}{4})+2n$

$\ \ \ \ \ \ \ \ =4(2T(\frac{n}{8})+\frac{n}{4})+2n=8T(\frac{n}{8})+3n$

$\ \ \ \ \ \ \ \ ...$

$\ \ \ \ \ \ \ \ =nT(1)+log(n)*n$

$\ \ \ \ \ \ \ \ =n*log(n)$

 

합병 정렬(Merge sort) 구현

#include <iostream>
using namespace std;

// 두 개의 하위 배열을 병합하는 함수
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;  // 왼쪽 하위 배열의 크기
    int n2 = right - mid;     // 오른쪽 하위 배열의 크기

    // 임시 배열 생성
    int L[n1], R[n2];

    // 원본 배열의 값을 각각 왼쪽과 오른쪽 임시 배열로 복사
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // 두 배열을 병합하여 정렬된 상태로 원래 배열에 다시 삽입
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 왼쪽 배열의 남은 요소 복사
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // 오른쪽 배열의 남은 요소 복사
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// Merge Sort 알고리즘
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        // 왼쪽과 오른쪽 배열에 대해 재귀적으로 정렬
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // 정렬된 두 배열을 병합
        merge(arr, left, mid, right);
    }
}

// 배열을 출력하는 함수
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    cout << "Given array is \n";
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    cout << "\nSorted array is \n";
    printArray(arr, arr_size);
    return 0;
}