stementor-sorting-mergesort-1.cpp

vector<int> merge_sort(vector<int>& arr) {
    int n = (int) arr.size();

    // 원소가 1개인 경우 이미 정렬이 완료됨
    if (n <= 1) {
        return arr;
    }

    // 부분배열을 구성
    vector<int> left = vector<int>(begin(arr), begin(arr) + (n / 2));
    vector<int> right = vector<int>(begin(arr) + (n / 2), end(arr));

    // 각 부분배열을 정렬
    left = merge_sort(left);
    right = merge_sort(right);

    // left, right 부분배열을 잘 병합하여 정렬된 상태로 돌려줌
    return merge(left, right);
}