归并排序

归并排序 - 分治思想（divide and conquer）

将有序的子序列合并最终得到完全有序的序列。

原理

二路归并

代码

public class MergeSort {

    public static void mergeSort(int[] array) {
        int[] tmpArray = new int[array.length];
        sort(array, tmpArray, 0, array.length - 1);
    }


    private static void sort(int[] array, int[] tmp, int startIndex, int endIndex) {
        if (endIndex <= startIndex) {
            return;
        }

        // 寻找切分位置
        int middleIndex = startIndex + (endIndex - startIndex) / 2;

        // 分解
        sort(array, tmp, startIndex, middleIndex);
        sort(array, tmp, middleIndex + 1, endIndex);

        // merge
        merge(array, tmp, startIndex, middleIndex, endIndex);

    }


    private static void merge(int[] array, int[] tmp, int startIndex, int middleIndex, int endIndex) {
        // 先复制要合并的数据
        for (int s = startIndex; s <= endIndex; s++) {
            tmp[s] = array[s];
        }

        int left = startIndex; // 左边首位下标
        int right = middleIndex + 1; // 右边首位下标


        while (left <= middleIndex && right <= endIndex) {
            if (tmp[left] < tmp[right]) {
                array[startIndex++] = tmp[left++];
            } else {
                array[startIndex++] = tmp[right++];
            }
        }

        while (left <= middleIndex) {
            array[startIndex++] = tmp[left++];
        }

        while (right <= endIndex) {
            array[startIndex++] = tmp[right++];
        }


    }

}

总结

时间复杂度\(O(nlg_n)\)

• 二叉树深度- 归并需要\(log_2n\) 次
• 两两归并需要扫描当前归并子序列的所有元素 （n）

稳定排序。