머지 소트

분할 정복

배열을 하나 또는 둘 까지 반으로 계속 쪼갠 다음 합치는 방식으로 이해하면 됨

int arr[100000]; // 입력받은 배열
int tmp[100000]; // 정렬에 필요한 임시 배열
void merge(int a, int b) {
    if (b == a) return;
    if (b - a == 1) {
        if (arr[a] > arr[b]) swap(arr[a], arr[b]);
        return;
    }
    int left = a;
    int mid = (a + b) / 2;
    int right = mid + 1;
    merge(a, mid);
    merge(mid + 1, b);
    int i = a;
    while (left != mid + 1 && right != b + 1) {
        if (arr[left] < arr[right]) tmp[i++] = arr[left++];
        else tmp[i++] = arr[right++];
    }
    if (left != mid + 1) while (i != b + 1) tmp[i++] = arr[left++];
    if (right != b + 1) while (i != b + 1) tmp[i++] = arr[right++];
    for (int j = a; j <= b; j++) arr[j] = tmp[j];
}