思路

图示

代码

算法

    private static int[] tempArr;

    /**
     * 归并排序
     *
     * @param data
     */
    public static void mergeOrder(int[] data) {
        tempArr = new int[data.length];
        mergeOrder(data, 0, data.length - 1);
    }

    private static void mergeOrder(int[] data, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = (start + end) / 2;
        // 排序左子区间
        mergeOrder(data, start, mid);
        // 排序右子区间
        mergeOrder(data, mid + 1, end);

        // 左右子区间归并
        // left：左区间开始位置，right：右区间开始位置
        int left = start, right = mid + 1, pos = left;
        while (left <= mid && right <= end) {
            tempArr[pos++] = data[left] < data[right] ? data[left++] : data[right++];
        }
        if (left <= mid) {
            System.arraycopy(data, left, tempArr, pos, mid - left + 1);
        }
        if (right <= end) {
            System.arraycopy(data, right, tempArr, pos, end - right + 1);
        }
        System.arraycopy(tempArr, start, data, start, end - start + 1);
    }

测试

    public static void main(String[] args) {
        int[] data = {5, 3, 4, 1, 2};
        mergeOrder(data);
        System.out.println(Arrays.toString(data));
    }

结果

[1, 2, 3, 4, 5]