[Algorithm - C++] Merge Sort

JeongChaeJin·2022년 9월 25일

How it works

전체 집합을 작은 크기 부분 집합으로 나눈다.
- 각 부분 배열이 하나의 원소만 가질 때 멈춘다.
작은 크기 집합을 오름 차순 or 내림 차순 정렬을 유지하며 합친다.

Code Review

merge_sort() function

template <typename T>
std::vector<T> merge_sort(std::vector<T> arr)
{

    if (arr.size() > 1)
    {
        auto mid = size_t(arr.size() / 2);
        auto left_half = merge_sort<T>(std::vector<T>(arr.begin(), arr.begin() + mid));
        auto right_half = merge_sort<T>(std::vector<T>(arr.begin() + mid, arr.end()));

        return merge<T>(left_half, right_half);
    }

    return arr;
}

partition

auto mid = size_t(arr.size() / 2);
auto left_half = merge_sort<T>(std::vector<T>(arr.begin(), arr.begin() + mid));
auto right_half = merge_sort<T>(std::vector<T>(arr.begin() + mid, arr.end()));

원소가 하나일 때 까지 분할하기 위해 재귀 호출을 수행한다.
여기서 분할은 부분 배열의 가운데 인덱스를 중심으로 2중 분할을 의미한다.

merge

return merge<T>(left_half, right_half);

위 partition을 하다 보면 마지막 재귀 깊이에서 원소가 하나만 남는 경우가 된다.
그 때 부터는 merge를 수행하며 left half, right half를 순서로 받는다.

merge() function

template <typename T>
std::vector<T> merge(std::vector<T> &arr1, std::vector<T> &arr2)
{
    std::vector<T> merged;

    auto iter1 = arr1.begin();
    auto iter2 = arr2.begin();

    while (iter1 != arr1.end() && iter2 != arr2.end())
    {
        if (*iter1 < *iter2)
        {
            merged.emplace_back(*iter1);
            ++iter1;
        }
        else
        {
            merged.emplace_back(*iter2);
            ++iter2;
        }
    }

    if (iter1 != arr1.end())
    {
        for (; iter1 != arr1.end(); ++iter1)
        {
            merged.emplace_back(*iter1);
        }
    }
    else
    {
        for (; iter2 != arr2.end(); ++iter2)
        {
            merged.emplace_back(*iter2);
        }
    }

    return merged;
}

sort

while (iter1 != arr1.end() && iter2 != arr2.end())
    {
        if (*iter1 < *iter2)
        {
            merged.emplace_back(*iter1);
            ++iter1;
        }
        else
        {
            merged.emplace_back(*iter2);
            ++iter2;
        }
    }

각각 오름차순으로 정렬하기위해 left array, right array 각 iterator를 통한 값의 비교를 통해 더 작은 원소를 먼저 emplace_back 한다.
각 iterator 중 마지막까지 도달하면 해당 sort 는 멈춘다.

sort 마무리

if (iter1 != arr1.end())
{
	for (; iter1 != arr1.end(); ++iter1)
	{
		merged.emplace_back(*iter1);
	}
}
else
{
	for (; iter2 != arr2.end(); ++iter2)
	{
		merged.emplace_back(*iter2);
	}
}

return merged;