数据结构与算法——归并排序

是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。

算法要点

1. 通过递归的模式，将序列不断的从中间拆分，直到不可拆分为止，这一步骤称为“分”
2. 通过递归的模式，将拆分后的两个序列通过对比两个序列的每个元素，将其合并到一起，直到所有序列都合并完成，这一步骤被称为“治”

动图演示

代码示例

package Sort;

public class Sort {
    /**
     * 归并排序
     *
     * @param data  int[] 数据
     * @param left  int 左节点
     * @param right int 右节点
     *
     * @return int[]
     */
    public int[] mergeSort(int[] data, int left, int right)
    {
        int middle = (left + right) / 2;
        if (right - left > 1) {
            //拆左侧的
            if (middle - left >= 1) {
                data = mergeSort(data, left, middle);
            }
            //拆右侧的
            if (right - middle >= 0) {
                data = mergeSort(data, middle + 1, right);
            }
        }
        //合并
        return mergeSort(data, left, middle, right);
    }

    protected int[] mergeSort(int[] data, int left, int middle, int right)
    {
        int[] temp = new int[data.length];

        int l = left;
        int m = middle + 1;
        int i = 0;
        while (l <= middle && m <= right) {
            if (data[l] > data[m]) {
                temp[i] = data[m];
                m++;
                i++;
            } else {
                temp[i] = data[l];
                l++;
                i++;
            }
        }

        while (l <= middle) {
            temp[i] = data[l];
            l++;
            i++;
        }

        while (m <= right) {
            temp[i] = data[m];
            m++;
            i++;
        }

        //往回填充
        for (int j = right; j >= left; j--) {
            data[j] = temp[i - 1];
            i--;
        }
        return data;
    }
}