面试算法：归并排序

题目

归并排序也是一种基于分治法的排序算法。为了排序长度为n的数组，需要先排序两个长度为n/2的子数组，然后合并这两个排序的子数组，于是整个数组也就排序完毕。

分析

归并排序可以用迭代代码实现。例如，输入一个长度为8的数组[4，1，5，6，2，7，8，3]，

• 可以先合并相邻的长度为1的子数组得到4个排序的长度为2的子数组。
• 然后合并相邻的长度为2的子数组得到2个排序的长度为4的子数组
• 最后合并相邻的长度为4的子数组，此时整个数组排序完毕

解

public class Test {
    public static void main(String[] args) {
        int[] nums = {4, 1, 5, 6, 2, 7, 8, 3};
        int[] result = sortArray(nums);
        for (int item : result) {
            System.out.println(item);
        }
    }

    public static int[] sortArray(int[] nums) {
        int length = nums.length;
        int[] src = nums;
        int[] dst = new int[length];
        for (int seg = 1; seg < length; seg += seg) {// 合并分段的长度
            for (int start = 0; start < length; start += seg * 2) {
                int mid = Math.min(start + seg, length);
                // i,j两个游标在遍历的时候，j可能先到达end，因为end可能取的是length的值
                int end = Math.min(start + seg * 2, length);
                int i = start, j = mid, k = start;
                while (i < mid || j < end) {
                    if (j == end || (i < mid && src[i] < src[j])) {
                        dst[k++] = src[i++];
                    }
                    else {
                        dst[k++] = src[j++];
                    }
                }
            }

            int[] temp = src;
            src = dst;
            dst = temp;
        }

        return src;
    }

}