AcWing 787. 归并排序

原题链接：https://www.acwing.com/problem/content/789/

归并算法采用双指针实现，模板实现起来也比较简单。

// merge sort in [left, right)
void merge_sort(int nums[], int left, int right) {
    if (right - left <= 1) return;
    
    int mid = (left + right) >> 1;
    
    merge_sort(nums, left, mid);
    merge_sort(nums, mid, right);
    
    int i = left, j = mid, k = 0;
    // i 和 j 不断移动取最小值，直到其中一个越界
    while (i < mid && j < right)
        if (nums[i] < nums[j]) tmp[k++] = nums[i++];
        else tmp[k++] = nums[j++];
    // 将剩下的部分拷贝到tmp中
    while (i < mid) tmp[k++] = nums[i++];
    while (j < right) tmp[k++] = nums[j++];
    // 从tmp拷贝回原数组
    for (i = left, j = 0; i < right; i++, j++) nums[i] = tmp[j];
}