Merge Sort

• Time : O(nlogn)
• Space : O(n)

c++

void dnc(vector<int>& A, int l, int r) {
    if(l == r) return;
    int m = (l + r) / 2;
    dnc(A, l, m);
    dnc(A, m + 1, r);
    
    vector<int> sorted;
    int i = l, j = m + 1;
    while(i <= m and j <= r) {
        if(A[i] < A[j]) sorted.push_back(A[i++]);
        else sorted.push_back(A[j++]);
    }
    while(i <= m) sorted.push_back(A[i++]);
    while(j <= r) sorted.push_back(A[j++]);
    for(auto& s : sorted) A[l++] = s;
}

vector<int> mergeSort(vector<int> array) {
    dnc(array, 0, array.size() - 1);
    return array;
}