归并排序Java

归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

其思想为：
分解：分解待排序的n个元素的序列成各具n/2个元素的子序列
解决：使用归并排序递归地排序两个子序列
合并：合并两个已排序的子序列以产生已排序的答案

归并排序的关键步骤为合并。

可以通过调用一个merge（int[] arr,int low,int mid,int high）过程来完成合并，其中arr为一个数组，low，mid，high为数组下标，假设数组中low--mid，mid+1--high均已排列好，此过程用于将之排列好为low--high的数组。

merge实现思路如下：
将传入的数组arr按照传入的数组下标从low到mid和从mid+1到high，依次将值复制到left和right两个数组，并为left和right末尾设置“哨兵”，用于标记数组末尾。因此left和right的长度均需在原有的基础上加一。
在得到left和right后，可将其视作牌面朝上、排列好的扑克牌，现在可以通过一个循环，每次取牌面最小的那张牌并插入到arr数组的low位置起直至high位置，即可实现两个数组的排列。这个过程前需将哨兵设置为无穷大，便于for循环的判断。

现在可将merge视作一个子程序，实现一个sort（int[] arr,int low,int high）来调用merge。
sort程序先判断low是否小于high，若是则将之分解为low--mid，mid+1--high两个数组，依次调用sort，最后调用merge来实现数组的归并。

Java实现如下：
MergeSort.java

public class MergeSort {
    public void sort(int[] arr, int low, int high) {
        if (low < high) {
            int mid = (low + high) / 2;
            sort(arr, low, mid);
            sort(arr, mid + 1, high);
            merge(arr, low, mid, high);
        }
    }

    void merge(int[] arr, int low, int mid, int high) {
        int[] left = new int[mid - low + 2];
        int[] right = new int[high - mid + 1];
        for (int i = 0; i < left.length - 1; i++) {
            left[i] = arr[low + i];
        }
        left[left.length - 1] = 2147483647;//哨兵
        for (int i = 0; i < right.length - 1; i++) {
            right[i] = arr[mid + i + 1];
        }
        right[right.length - 1] = 2147483647;
        int j = 0;
        int k = 0;
        for (int i = low; i <= high; i++) {
            if (left[j] <= right[k]) {
                arr[i] = left[j];
                j++;
            } else {
                arr[i] = right[k];
                k++;
            }
        }
    }
}

Main.java

public class Main {
    public static void main(String[] args) {
        int[] arr={2,3,6,5,4,7,8,9,5,2,1,4,5,2,3,6,9,8,7,1,0,2,3,6,45,4,5,6,5,8,5};
        System.out.println(Arrays.toString(arr));
        new MergeSort().sort(arr, 0, arr.length-1);
        System.out.println("  ||\n  ||\n  \\/");
        System.out.println(Arrays.toString(arr));
    }
}

测试结果

[2, 3, 6, 5, 4, 7, 8, 9, 5, 2, 1, 4, 5, 2, 3, 6, 9, 8, 7, 1, 0, 2, 3, 6, 45, 4, 5, 6, 5, 8, 5]
||
||
\/
[0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 8, 8, 8, 9, 9, 45]

参考自《算法导论》，如有纰漏感谢指正