归并排序

思路很简单，就是不断的分区，分到不可在分的时候就合并，很适合用递归，可惜不是原地排序,用了额外空间，因此没有快排火，代码思路简单，数组合入，与复制要注意边界，我就是这样被坑的

public class Client {
    public static void main(String[] args) {
        int[] result = sortArray(new int[]{5, 1, 7, 2, 0, 9});
        for (int value : result) {
            System.out.println(value);
        }
    }
<pre><code>public static int[] sortArray(int[] nums) {
    sort(nums, 0, nums.length - 1);
    return nums;
}

public static void sort(int[] nums, int start, int end) {
    if (start &gt;= end)
        return;

    int middle = (start + end) / 2;
    sort(nums, start, middle);

    sort(nums, middle + 1, end);

    merge(nums, start, middle, end);
}


public static void merge(int[] num, int start, int middle, int end) {
    int[] result = new int[end - start + 1];
    int index1 = start;
    int index2 = middle + 1;
    int count = 0;
    while (index1 &lt;= middle &amp;&amp; index2 &lt;= end) {
        if (num[index1] &lt; num[index2]) {
            result[count++] = num[index1++];
        } else {
            result[count++] = num[index2++];
        }
    }

    while (index1 &lt;= middle) {
        result[count++] = num[index1++];
    }

    while (index2 &lt;= end) {
        result[count++] = num[index2++];
    }

    count = 0;
    while (start &lt;= end) {
        num[start++] = result[count++];
    }
}

}