老师，在 merge() 函数中是对两个已经排好序的数组进行归并 ，那么这两个数组是怎么排好序的 没怎么懂呢？？？

Answer 1

liuyubobobo 2017-05-25 01:05:00

miniyao回答的完全正确：）

MergeSort在最初会不断的细分整个数组，当数组的长度为1，即整个数组不需要排序也是有序的情况下开始进行merge，将两个包含有1个元素的数组merge成了一个有序的2个元素的数组；之后将两个有序的包含2个元素的数组合并成一个有序的包含4个元素的数组；之后将两个有序的包含4个元素的数组合并成一个有序的包含8个元素的数组...依次类推。

如果还不理解整个过程，不要只对着代码生想。实际使用一个小数据量的测试用例，比如只包含8个元素的无序数组，然后使用debug一步一步跟着程序走一遍，观察程序在运行每一行代码之后数据和各种辅助的变量具体是怎样变化的，和自己的理解在哪里有偏差。这是非常好的理解算法运行机制的形式。千万不要怕麻烦！

miniyao对这个问题的具体回答比我更清晰，如果理解了，请采纳miniyao的回答：）

• 提问者 wang_liu #1

  非常感谢！谢谢老师的回答

Answer 2

ahak 2017-05-25 00:45:37

递归思想啊，将问题分而治之，解决最小的问题并迭代就ok了

private static void sort(Comparable[] arr, int l, int r) {
    if (l >= r)
        return;

    int mid = l + (r - l) / 2;
    sort(arr, l, mid);
    sort(arr, mid + 1, r);
    merge(arr, l, mid, r);
}

如代码所示，每次传进私有函数sort（对应老师的__mergesort函数）的是一个片段arr[l...r]，这是显而易见的。

当我将arr,0,n-1传进来时，代表我要排序的整个算法进来了，注意mid=l+(r-l)/2是我改进了一下防止mid溢出的；

这里的sort递归分别把整个数组的前半部分和后半部分再次sort，再各自分为一半。你要问的是那我们如何排序的，考虑当我们的函数进行到最后阶段，及base case l >= r之前，也就是r - l = 1的情况，即当我的数组片段长度为1时，仅有一个元素，不需要sort了，这里的merge就派上用场了，将我的元素合并起来，而且都是排序好的元素。

这里sort(arr,0,n-1) -> 下一层sort -> ... -> sort(); merge，你看，进入第一次sort后会无限的进入sort，直到满足base case l >=r，这就是堆栈了！弹出的时候会满足最后进去的式子，也就是最底层的merge后依次弹出，这时我们的数据自然也就排序好了！

如果看懂了。。请采纳

• liuyubobobo #1

  感谢你的回答：）

• 提问者 wang_liu #2

  感谢同学的回答，非常感谢呢。