[알고리즘] Merge Sort - Proof & Time Complexity

* 본 글은 2023학년도 2학기에 수강한 '알고리즘' 과목 강의 내용을 함께 정리하여 작성하였습니다.

 

Proof of Correctness of Sorting

---

'Sorting이 되었다'라고 말할 수 있으려면 어떠한 조건들이 만족되어야 하는가?

 

- 입력 값 : a[0], a[1], ... , a[n-1]

- sorting이 끝난 후 배열에 저장된 값 : b[0], b[1], ... , b[n-1]

 

조건 1:

값이 없어지거나, 새로 생기면 안된다. (집합 조건)

{a[0], a[1], ... , a[n-1]} = {b[0], b[1], ... , b[n-1]}

 

조건 2:

값 기준, 오름차순 정렬된 순서로 저장되어 있어야 한다.

b[0] < b[1] < ... < b[n-1]

 

 

Merge Sort

---

Merge Algorithm을 사용하는 O(NlogN)짜리 sorting 알고리즘이다.

 

main idea

sorting 된 배열 두 개를 합하여, 최종 sorting 된 배열 하나를 만들자!

 

1. 앞에서부터 차례대로 보면서, 두 배열 각각에 저장된 값들을 하나씩 비교한다.

2. 둘 중 더 작은 것을 목적 배열로 옮긴다.

→ Merge Algorithm은 O(N)이다.

 

 

Recursive Merge Sort

---

입력 배열 arr에는 같은 값이 없고, size = 0인 경우는 호출하지 않는다고 가정하자.

void mergeSort(int arr[], int size) {
    if (size == 1) {
        return;
    }

    int tempArr[size];
    for (int i = 0; i < size; ++i) {
        tempArr[i] = arr[i];
    }

    int half = size / 2;
    mergeSort(tempArr, half);
    mergeSort(tempArr + half, size - half);

    // merge two halves to arr
    int i = 0, j = half;
    int k = 0;
    while (i < half && j < size) {
        if (tempArr[i] < tempArr[j]) {
            arr[k++] = tempArr[i++];
            continue;
        }
        arr[k++] = tempArr[j++];
    }
    while (i < half) {
        arr[k++] = tempArr[i++];
    }
    while (j < size) {
        arr[k++] = tempArr[j++];
    }
}

추가적인 배열(tempArr)이 반드시 하나 있어야 한다. → memory 추가 소모

 

Proof by Induction

주장:

mergeSort() 함수를 통해서 sorting이 된다.

 

Base:

n = 1

아무것도 진행하지 않아도 된다. → True

 

Step:

n/2일 때 mergeSort() 함수가 sorting에 성공한다면, n일 때에도 mergeSort() 함수가 sorting에 성공한다.

 

즉, 재귀호출이 끝난 후에 다음 두 조건이 성립한다면,

- tempArr[0] < tempArr[1] < ... < tempArr[n/2 - 1]

- tempArr[n/2] < tempArr[n/2 + 1] < ... < tempArr[n-1]

함수가 끝났을 때 arr[0] < arr[1] < arr[2] < ... < arr[n-1]이 성립한다.

 

이는 merge의 정확성에 의해서 성립한다.

1. merge는 합집합을 한다.

2. merge는 sorting 결과를 만들어 낸다.

 

Time Complexity

T(n)

= n + 2T(n/2)

= n + 2(n/2 + 2(n/4 + 2T(n/8)))

= ...

 

∴ O(NlogN)