C++中的归并排序函数

Question

我有下面这段代码，它代表一个合并排序函数

/* perform merge sort */
void merge_sort(int arr[], int left, int right) {
    if (left < right) {
        int middle = left + (right - left) / 2;
        merge_sort(arr, left, middle);
        merge_sort(arr, middle + 1, right);
        merge(arr, left, middle, right);
    }
}

此merge_sort(arr, middle + 1, right);的用途是什么

Answer 1

merge sort algorithm的基本思想是将要排序的序列一分为二，分别排序，然后将它们合并在一起。这通常是递归完成的，如本例所示。因此，必须有两个递归调用，每个递归调用对应于序列的一半。

如果不存在merge_sort(arr, middle+1, right);调用，则算法将不完整，排序将不起作用。

作为实验，您可以尝试使用您发布的合并排序函数编写一个示例程序。在有问题的行和不带行的情况下尝试一下，看看会得到什么结果。