java.合并排序

原理：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子 序列段间有序。若将两个有序表合并成一个有序表，称为二路归并

时间复杂度 O(NlogN)
空间复杂度 O(N）
稳定性：稳定

源码：

    // 合并排序
    public static void mergeSort(int[] array) {
        mergeSortHelper(array, 0, array.length);
    }

    private static void mergeSortHelper(int[] array, int left, int right) {
        if (left >= right || right - left == 1) {
            return;
        }
        int mid = (left + right) / 2;
        mergeSortHelper(array, left, mid);
        mergeSortHelper(array, mid, right);
        // 合并两个数组操作 merge
        merge(array, left, mid, right);
    }

    private static void merge(int[] array, int left,
                                int mid, int right) {
        int length = right - left;
        int[] output = new int[length];

        int outputIndex = 0;

        int i = left;
        int j = mid;
        while (i < mid && j < right) {
            if (array[i] <= array[j]) {
                output[outputIndex++] = array[i++];
            } else {
                output[outputIndex++] = array[j++];
            }
        }
        while (i < mid) {
            output[outputIndex++] = array[i++];
        }
        while (j < right) {
            output[outputIndex++] = array[j++];
        }

        for (int k = 0; k < length; k++) {
            array[left + k] = output[k];
        }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44