Insertion sort is used for small arrays in merge sort-Python Tutorial-php.cn

Insertion sort is used for small arrays in merge sort

巴扎黑

Release： 2016-12-08 11:33:16

Original

1558 people have browsed it

The complexity of pure merge sort is: O(nlgn), while the time complexity of pure insertion sort is: O(n^2). Merge sort is used when the amount of data is large

, but when n is small, insertion sort may run faster. Therefore, in merge sort, when the subproblem becomes small enough, using insertion sort to make the recursive leaves thicker can speed up the sorting. So how do you measure if this is small enough? Please see below:

I won’t prove these, it’s relatively simple:

A, insertion sort can sort each n/k sublist of length k in O(nk) time in the worst case

B , these sub-tables can be merged in O(nlg(n/k)) time in the worst case

C, the worst-case running time complexity of the revised algorithm is O(nk + nlg(n/k ))

Then, O(nk+nlg(n/k))=O(nlgn). The maximum can only be k=O(lgn). The first term on the left side of the equation is a higher-order term. If k is greater than lgn, it is more complex than merge sort. The left side can be written as nk+nlgn-nlgk. When k is equal to lgn, it is 2nlgn-nlglgn. Ignoring the constant coefficient, it is the same as merge sort.

Final conclusion: When k

from at003_insertsort import insertSort
from math import log
__author__ = &#39;Xiong Neng&#39;
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)

Copy after login