[백준]2751-수 정렬하기 2(설명X, 머지소트)

#include <cstdio>
 
void mergeSort(int n, int* array);
void merge(int h, int m, int* U, int* V, int* S);
 
int main() {
    int input;
    scanf("%d", &input);
    int* number = new int[input];
    for (int i = 0; i < input; i++)
        scanf("%d", &number[i]);
 
    mergeSort(input, number);
    for (int i = 0; i < input; i++)
        printf("%d\n", number[i]);
 
    delete[] number;
}
 
void mergeSort(int n, int* array) {
    if (n > 1) {
        const int h = n / 2;
        const int m = n - h;
 
        int* U = new int[h];
        int* V = new int[m];
 
        for (int i = 0; i < h; i++)
            U[i] = array[i];
        for (int i = 0; i < m; i++)
            V[i] = array[i + h];
 
        mergeSort(h, U);
        mergeSort(m, V);
        merge(h, m, U, V, array);
        delete[] U, V;
    }
}
 
void merge(int h, int m, int* U, int* V, int* S) {
    int i = 0, j = 0, k = 0;
    while (i < h && j < m) {
        if (U[i] < V[j]) {
            S[k] = U[i];
            i++;
        }
        else {
            S[k] = V[j];
            j++;
        }
        k++;
    }
    if (j < m)
        while (j < m)
            S[k++] = V[j++];
    else
        while (i < h)
            S[k++] = U[i++];
}

nlgn인 정렬로 시간제한 통과할 수 있다고 써 있었는데, 그냥 퀵소트 돌려봤는데 시간초과 떴다.

그래서 머지소트 만들어서 통과시켰다.