如何理解归并排序中的递归使得两个有序数组有序再按比较首元素合并？

Question

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会等于几？

Answer 1

归并排序的解空间就是一个二叉树，递归求解过程就像是一个深度优先搜索算法，你要了解递归函数的堆栈过程

按树结构来思考，mergesort就像是创建一个结点，如果这个结点中（lo<hi），那么就会创建两个子结点，就这样一直创建下去，就会得到一颗二叉树。
mergesort(arr,lo, mid);
mergesort(arr, mid + 1, hi);
merge(arr, lo, mid, hi);

你不觉得这样的写法就像树的先序遍历吗？

至于你说i加了几次，显而易见，有多少个结点（mergesort函数）就加多少次