void mergesort(int arr[],int lo,int hi) {
int mid = (lo+hi) >> 1;
if (lo<hi){
mergesort(arr,lo, mid);
mergesort(arr, mid + 1, hi);
merge(arr, lo, mid, hi);
}
}
搞不懂mergesort(arr,lo,mid)怎么就让左边的元素有序了?
我的一些理解是,mergesort这个递归函数的出路是lo==hi,每一次调用自身,相当于把mid
不断除以2,按照这样,我们第一个递归调用应该得到一个元素的区间(假设
lo==0)[0,)这是数组首元素。然后再去执行 mergesort(arr,lo, mid),又得到一个
元素的区间。再去执行merge(arr, lo, mid, hi),然后进行两个元素的比较,排序。
我感觉我这样的理解显然是错误的,我一直弄不懂一个递归函数的下面的执行语句究竟是怎么执行的。比如我假设有一个全局变量i放到了第一个mergesort下面,让它进行自加,究竟什么时候才会i++一次呢?i会等于几?