純歸併排序的複雜度為： 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時，就是2nlgn-nlglgn.忽略恆定係數，則與歸併排序是一樣的。
最後結論： 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__ == '__main__':
aa = [4, 2, 5, 1, 6, 3, 7, 9, 8]
mergeSort(aa)
print(aa)
