[PS] Merge Sort 구현 (C++)

한국에 돌아와서 취업준비를 하며 코딩테스트 공부를 다시 시작했다. 이왕 코테 공부 시작한 김에 PS를 더 깊이 파보고자 문제를 풀며 배운 기초적인 내용들을 정리하려고 한다.

Merge Sort 는 정렬 알고리즘 중에 Quick Sort, Heap Sort 와 같이 빠른 정렬 알고리즘이다. 시간복잡도는 O(NlogN).

동작원리

Merge Sort 의 기본적인 동작 원리는 divide and conquer 로, 리스트를 쪼개가며 더 작은 단위로 나눠 각각을 해결 한 후 합치는 방식이다.

[10, 5, 7, 29, 13, 1, 3, 9] 라는 리스트가 있다고 가정할 때, 아래와 같은 분할 과정을 거친다:

[10, 5, 7, 29, 13, 1, 3, 9] ->

[10, 5, 7, 29], [13, 1, 3, 9] ->

[10, 5], [7, 29], [13, 1], [3, 9] ->

[10], [5], [7], [29], [13], [1], [3], [9]

N/2 의 크기의 리스트로 더이상 분할 할 수 없을 때까지 분할을 한 후, 이웃한 하위 리스트와 크기 비교를 하며 결합하면 된다!

[10], [5], [7], [29], [13], [1], [3], [9] ->

[5, 10], [7, 29], [1, 13], [3, 9] ->

[5, 7, 10, 29], [1, 2, 9, 13] ->

[1, 2, 5, 7, 9, 10, 13, 29]

이때, 합병을 할 때는 이미 두개의 하위 리스트가 각각 정렬이 되어있는 상태이기 때문에 각 리스트의 첫번째 element 부터 비교하며 새로운 리스트에 넣으면 된다. 작성 편의상 리스트의 길이가 짝수인 경우를 예시로 들었지만, 홀수여도 동일한 방식으로 구현이 가능하다.

Merge Sort 의 장단점

장점

데이터 분포와 관계없이 안정적인 sorting 이 가능하다. 정렬에 걸리는 시간은 O(NlogN) 로 동일.

단점

array 의 형태로 구성할 경우 in-place sorting 이 불가능하다. 즉, 추가적인 리스트가 필요하다.
- linked list 로 구성하면 link index 만 변경하면 되므로 in-place sorting 이 가능하긴 함.

pseudo code

C++ 로 merge sort 를 구현하기에 앞서 pseudo code 를 작성해 보았다.

function merge(left, right):
    result = []
    i, j = 0, 0

    # left, right 리스트를 순서대로 비교하며 result list 를 채워넣는다.
    while i < length of left and j < length of right:
        if left[i] < right[j]:
            result.append(left[i])
            i++

        else:
            result.append(right[j])
            j++

    # right 리스트가 다 비워지면, left 리스트의 남은 element 들을 result list 에 채워넣는다.
    while i < length of left:
        result.append(left[i])
        i++

    # left 리스트가 다 비워지면, right 리스트의 남은 element 들을 result list 에 채워넣는다.
    while j < length of right:
        result.append(right[j])
        j++

    return result

function mergeSort(arr):
    if length of arr <= 1:
        return arr

    mid = length of arr / 2
    left = arr[0:mid] # 왼쪽 sub list
    right = arr[mid:] # 오른쪽 sub list

    # 재귀함수를 통해 길이가 1이 될때까지 나눈다.
    sortedLeft = mergeSort(left)
    sortedRight = mergeSort(right)

    merged = merge(sortedLeft, sortedRight)

    return merged

merge sort 는 보통 recursion 을 통해 구현된다. mergeSort 함수 내에서 리스트를 각 하위 리스트의 길이가 1이 될때까지 나눈 후 merge 함수를 통해 합쳐지는 로직이다.

C++ 구현

#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 = new int[n1];
    int* R = new int[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++];
        else arr[k++] = R[j++];
    }

    while(i < n1) arr[k++] = L[i++];
    while(j < n2) arr[k++] = R[j++];

    delete[] L;
    delete[] R;
}

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);
    }
}

int main()
{
    int arr[] = {10, 5, 7, 29, 13, 1, 3, 9};
    int n = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, n - 1);

    for(int i = 0; i < n; i++) cout << arr[i] << " ";
}