작은 배열에 삽입 정렬을 사용한 병합 정렬

순수 병합 정렬의 복잡도는 O(nlgn)이고 순수 삽입 정렬의 시간 복잡도는 O(n^2)입니다. 데이터의 양이 많을 때는 병합 정렬

을 사용하지만, n이 작을 때는 삽입 정렬이 더 빨리 실행될 수 있습니다. 따라서 병합 정렬에서는 하위 문제가 충분히 작아지면 삽입 정렬을 사용하여 재귀 리프를 더 두껍게 만드는 것이 정렬 속도를 높일 수 있습니다. 그렇다면 이것이 충분히 작은지 어떻게 측정합니까? 아래를 참조하세요:

증명하지는 않겠습니다. 비교적 간단합니다.

삽입 정렬은 최악의 경우 n/k 하위 목록에서 O(nk) 시간에 각 길이 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)