归并排序中对小数组采用插入排序

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)