C语言，二路归并排序，递归调用到底是怎么调用的？求详解！

Question

void merge_sort(int arr[], unsigned int first, unsigned int last){
int mid = 0; if(first<last){ mid = (first+last)/2; /* 注意防止溢出 */ /*mid = first/2 + last/2;*/ //mid = (first & last) + ((first ^ last) >> 1); merge_sort(arr, first, mid); merge_sort(arr, mid+1,last); merge(arr,first,mid,last); } return;}这二路归并到底是把一路调用完！还是两路一起调用，怎么理解啊！我对递归理解不了。。。。

Answer 1

程序代码都是顺序执行的，当然是把一路调用完再做第二路调用，最后把排好序的2路进行合并；

在排序每一路的时候也是使用归并的方式，把一路分成2路，层层深入。

理解的话，你可以这样：

比如8个数，你从上到下竖着排成一列，然后中间一条横线分割。

横线上面的部分再从中间分割成2部分，2部分放在第二列；

依次往后分割。得到形如这样的图：

然后按照红色箭头先按A反推一层，再按B向下一层，这样就会合并一次产生排好序的前一层。如此反复，这就是递归实际的执行流程。