/*
5.归并排序
最佳情况：T(n) = O(n)
最差情况：T(n) = O(nlogn)
平均情况：T(n) = O(nlogn)
*/

/*
将两个有序的数组合并
*/
void toMerge(int* arrays, int l, int mid, int r, int* temp) {
    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r) {
        if(arrays[i] <= arrays[j]) {
            temp[k++] = arrays[i++];
        } else {
            temp[k++] = arrays[j++];
        }
    }
    while(i <= mid) {
        temp[k++] = arrays[i++];
    }
    while(j <= r) {
        temp[k++] = arrays[j++];
    }
    for(int i = 0; i < k; i++) {
        arrays[l + i] = temp[i];
    }
}

/*
递归
*/
void mergesort(int* arrays, int l, int r, int* temp) {
    if(l < r) {
        int mid = (l + r) / 2;
        mergesort(arrays, l, mid, temp);
        mergesort(arrays, mid + 1, r, temp);
        toMerge(arrays, l, mid, r, temp);
    }
}

void mergeSort(int* arrays, int n) {
    int* temp = new int[n];
    mergesort(arrays, 0, n - 1, temp);
}