归并排序中，归的部分很好理解，并的部分稍微复杂：

    /**
     * 将两个数组进行归并，归并前面2个数组已有序，归并后依然有序
     *
     * @param array  数组对象
     * @param left   数组左侧的第一个元素的索引
     * @param center 数组左侧的最后一个元素的索引，center+1是数组右侧第一个元素的索引
     * @param right  数组右侧最后一个元素的索引
     */
    public static void merge(int[] array, int left, int center, int right) {
        int[] tmpArr = new int[array.length];           // 临时数组
        int mid = center + 1;                           // 右数组第一个元素索引
        int third = left;                               // third 记录临时数组的索引
        int tmp = left;                                 // 缓存左数组第一个元素的索引
        while (left <= center && mid <= right) {
            if (array[left] <= array[mid])              // 从两个数组中取出最小的放入临时数组
                tmpArr[third++] = array[left++];
            else
                tmpArr[third++] = array[mid++];
        }
        while (mid <= right)                            // 剩余部分依次放入临时数组（实际上两个while只会执行其中一个）
            tmpArr[third++] = array[mid++];
        while (left <= center)
            tmpArr[third++] = array[left++];
        while (tmp <= right)                            // 将临时数组中的内容拷贝回原数组中
            array[tmp] = tmpArr[tmp++];                 // （原left-right范围的内容被复制回原数组）
    }

主要逻辑就是：把原数组分成左部分和右部分，从左到右分别取两部分中较小的那个元素，复制到临时数组中。两部分总要一个先到尽头，那么最后就有且仅有剩余的另一部分，那么把这剩余的部分原样复制到临时数组（代码中左右两部分的复制逻辑都有，但是每次只会进入一个循环）。最后把临时数组复制回原数组。

对比快速排序，可以看到归并排序多了很多元素的复制过程，这导致归并排序期望时间的常数部分比较大。

还有个问题是归并的归是归到什么时候？如下代码：

    public static void mergeSort(int[] array, int left, int right) {
        if (left >= right)
            return;
        int center = (left + right) / 2;                 // 找出中间索引。最后left=1，right=2，center=1
        mergeSort(array, left, center);                  // 对左边数组进行递归，最后mergeSort array,1,1
        mergeSort(array, center + 1, right);             // 对右边数组进行递归，最后mergeSort array,2,2
        merge(array, left, center, right);               // 合并 1,1,2
    }

当左侧还剩数组元素0,1,2时，center=1，那么会继续归为0,1和2,2

0,1又可以进一步归，其中center=0，所以会归为0,0和1,1。之后并方法按从小到大合并两数组后，继续和第一步的2,2数组进行合并。

可以简单看出，归方法把大数组分割成两个小数组，它们的长度最多相差1。

顶起来！

人生有风险，入世需谨慎

...

彪悍的人生不需要解释

如果你不能给你的女人穿上嫁衣，那么千万别停下你解开她衣扣的手！

如果你不能给你的女人穿上嫁衣，那么千万别停下你解开她衣扣的手！

为何要放弃治疗

怀才就像怀孕，时间久了才能让人看出来。

你帅呆了酷毕了简直无法比喻了，如果把你失去了，肠子都要悔断了生活不能继续了感情缺乏甜蜜了地球也没吸引力了！

脑筋急转弯：甲乙丙丁俺，上山去砍柴，遇到一泡屎，甲乙丙丁没踩着，谁踩了？

你造么

虽然不曾见面，但你给我的感觉就如老朋友一样，亲切随和，让人舒心感动。谢谢你陪我聊天的日子！

星星月亮天上挂，嫦娥奔月了牵挂，牛郎织女谈情话，月老红娘是神话，有个笨蛋不说话，眯着眼睛看电话。

有钱人终成眷属。

请楼主吃麻辣烫可好