挿入ソートはマージソートの小さな配列に使用されます

純粋なマージソートの計算量は O(nlgn) ですが、純粋な挿入ソートの時間計算量は O(n^2) です。データ量が多い場合にはマージソートが使用されます

が、nが小さい場合には挿入ソートの方が高速に実行される場合があります。したがって、マージ ソートでは、部分問題が十分に小さくなったときに、挿入ソートを使用して再帰リーフを太くすると、ソートを高速化できます。では、これが十分小さいかどうかをどのように測定すればよいでしょうか? 以下を参照してください:

これらは証明しませんが、比較的単純です:

A、挿入ソートは、最悪の場合、O(nk) 時間で長さ k の各 n/k サブリストをソートできます

B、これらのサブリストは、テーブルは最悪の場合 O(nlg(n/k)) 時間でマージできます

C、修正されたアルゴリズムの最悪の場合の実行時間の複雑さは O(nk + nlg(n/k )) です

そして、 O(nk+nlg(n/k))=O(nlgn) 最大値は k=O(lgn) のみです。式の左側の最初の項は高次の項です。 k が lgn より大きい場合、マージ ソートよりも複雑になります。左辺は nk+nlgn-nlgk と書けます。k が lgn の場合、定数係数を無視すると、マージソートと同じになります。

最終結論: k

from at003_insertsort import insertSort
from math import log
__author__ = 'Xiong Neng'
def mergeSort(seq):
    mergeSortRange(seq, 0, len(seq) - 1, log(len(seq)) - 1)
def mergeOrderedSeq(seq, left, middle, right):
    """
    seq: 待排序序列
    left <= middle <= right
    子数组seq[left..middle]和seq[middle+1..right]都是排好序的
    该排序的时间复杂度为O(n)
    """
    tempSeq = []
    i = left
    j = middle + 1
    while i <= middle and j <= right:
        if seq[i] <= seq[j]:
            tempSeq.append(seq[i])
            i += 1
        else:
            tempSeq.append(seq[j])
            j += 1
    if i <= middle:
        tempSeq.extend(seq[i:middle + 1])
    else:
        tempSeq.extend(seq[j:right + 1])
    seq[left:right + 1] = tempSeq[:]
def mergeSortRange(seq, start, end, threshold):
    """
    归并排序一个序列的子序列
    start: 子序列的start下标
    end: 子序列的end下标
    threshold: 待排序长度低于这个值，就采用插入排序
    """
    if end - start < threshold:
        tempSeq = seq[start: end + 1]
        insertSort(tempSeq)
        seq[start: end + 1] = tempSeq[:]
    elif start < end:  # 如果start >= end就终止递归调用
        middle = (start + end) / 2
        mergeSortRange(seq, start, middle, threshold)  # 排好左边的一半
        mergeSortRange(seq, middle + 1, end, threshold)  # 再排好右边的一半
        mergeOrderedSeq(seq, start, middle, end)  # 最后合并排序结果
if __name__ == &#39;__main__&#39;:
    aa = [4, 2, 5, 1, 6, 3, 7, 9, 8]
    mergeSort(aa)
    print(aa)