递归调用在合并排序中实际上是如何工作的?

Question

void mergeSort(int arr[], int l, int r) { 
if (l < r) { 
int m = l + (r - l) / 2; 
mergeSort(arr, l, m); 
mergeSort(arr, m + 1, r); 
merge(arr, l, m, r); 
} 
} 

我明白mergesort函数如何将数组分解为单个元素，但merge函数不是只调用一次吗？

Answer 1

编辑：merge函数不只是连接两个数组。它扫描阵列并逐个添加到新阵列。 示例：[2, 4, 5, 6]和[1, 3, 7, 8]。首先比较 2 和 1。1 更小，所以我们把合并的数组作为第一个元素。然后比较 2 和 3,2 更小，所以他是合并数组中的下一个元素。现在比较 3 和 4 等。 您可以使用循环或递归实现merge。真的不重要...

您没有显示merge函数的任何实现，它超出了您发布的代码。