[boj] (s5) 2751 수 정렬하기 2 (합병 정렬)

합병 정렬을 이용해 수를 정렬하는 문제
문제 링크

1. 반으로 쪼개 왼쪽 부분 & 오른쪽 부분을 각각 mergeSort (분할 후 합병하는 함수)에 재귀적 호출
2. 이후 merge(합병)를 통해 배열 원소의 크기를 비교하여 새로운 배열에 저장
3. 정렬된 새로운 배열을 본래 배열에 옮겨 저장

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> arr;
int tmp[1000001];

void merge(int left, int mid, int right)
{
    int x = left, y = mid + 1, k = left;

    while(x <= mid || y <= right)
    {
        if(x <= mid && y <= right)
        {
            if(arr[x] <= arr[y]) tmp[k] = arr[x++];
            else tmp[k] = arr[y++];
        }
        else if(x <= mid && y > right)
        {
            tmp[k] = arr[x++];
        }
        else if (x > mid && y <= right)
        {
            tmp[k] = arr[y++];
        }

        k++;
    }

    for(int i=left;i<=right;i++)
    {
        arr[i] = tmp[i];
    }
}

void mergeSort(int left, int right)
{
    if(left >= right) return;

    int mid = (left + right) / 2;
    // 분할
    mergeSort(left, mid);
    mergeSort(mid + 1, right);
    // 합병
    merge(left, mid, right);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        int num;
        cin >> num;
        arr.push_back(num);
    }

    mergeSort(0, N-1);

    for (int i = 0; i < N; i++)
    {
        cout << arr[i] << '\n';
    }

    return 0;
}