归并排序和直接插入排序结合的排序算法

思路：
先利用直接插入排序求得较长的有序子序列，然后再两两归并。
参考博客：
https://blog.csdn.net/NumberOneStudent/article/details/105209572
代码：

class Solution {
    public static void main(String[] args) {
        int[] a = {55, 60,40,10,80,65,15,5,75};
        MergeAndInsertModel.mergeAndInsertSort(a, 0, a.length-1);
        for (int i:a){
            System.out.print(i + " ");
        }
    }
}

class MergeAndInsertModel {
    public static void mergeAndInsertSort(int[] array, int from, int to) {
        if(from>=to){
            return;
        }
        if (to - from + 1 <= lg(array.length)) {
            insertionSort(array, from, to);
        } else {
            int middle = (to + from) >> 1;
            mergeAndInsertSort(array, from, middle);
            mergeAndInsertSort(array, middle + 1, to);
            mergeSort(array, from, middle, to);
        }
    }
    // 插入排序
    private static void insertionSort(int[] array, int from, int to) {
        for (int i = from + 1; i <= to; i++) {
            int key = array[i];
            int j = i - 1;
            while (j >= from && key < array[j]) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = key;
        }
    }
    private static void mergeSort(int[] array, int from, int middle, int to) {
        int[] leftArray = new int[middle - from + 1];
        int[] rightArray = new int[to - middle];
        System.arraycopy(array, from, leftArray, 0, leftArray.length);
        System.arraycopy(array, middle + 1, rightArray, 0, rightArray.length);
        int idxL = 0;
        int idxR = 0;
        int idx= from;
        while(idxL< leftArray.length && idxR<rightArray.length) {
            if (leftArray[idxL] <= rightArray[idxR]) {
                array[idx] = leftArray[idxL++];
            } else {
                array[idx] = rightArray[idxR++];
            }
            idx++;
        }
        if (idxL < leftArray.length) {
            System.arraycopy(leftArray, idxL, array, idx, leftArray.length - idxL);
        }
        if (idxR < rightArray.length) {
            System.arraycopy(rightArray, idxR,  array, idx, rightArray.length - idxR);
        }
    }

    //计算以2为底的对数
    private static double lg(double n) {
        return Math.log(n) / Math.log(2);
    }
}


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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67