Python集計ソートアルゴリズム

Num 01->定義
集計ソートは分治法を採用する非常に典型的な応用である.集計ソートの考え方は,まず配列を再帰的に分解し,配列を統合することである.
配列を最小に分解した後、2つの秩序配列をマージします.基本的な考え方は、2つの配列の一番前の数を比較し、小さい人はまず誰を取り、取った後、対応するポインタは1つ後ろに移動します.次に、ある配列が空になるまで比較し、最後に別の配列の残りの部分をコピーすればよい.
Num 02->Pythonコードで実現

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Author  : xiaoke


def merge_sort(alist):
    """    """
    n = len(alist)
    #          
    if n == 1:
        return alist
    #          
    mid = n // 2
    #              
    left_sorted_li = merge_sort(alist[:mid])
    for x in left_sorted_li:
        print("   =", x, end=" ")
    print(" ")
    #              
    right_sorted_li = merge_sort(alist[mid:])
    for y in right_sorted_li:
        print("   =", y, end=" ")
    print(" ")
    return merge(left_sorted_li, right_sorted_li)


#           ，          
def merge(left_sorted_li, right_sorted_li):
    #         ，      0  
    left, right = 0, 0
    merge_result_li = []

    left_n = len(left_sorted_li)
    right_n = len(right_sorted_li)
    #      
    while left < left_n and right < right_n:
        #       ，         
        if left_sorted_li[left] <= right_sorted_li[right]:
            merge_result_li.append(left_sorted_li[left])
            left += 1
        else:
            merge_result_li.append(right_sorted_li[right])
            right += 1

    #                  ，         
    #                           ，      
    #    null,     [],       ，[1,2]+[]=[1,2]
    merge_result_li += left_sorted_li[left:]
    merge_result_li += right_sorted_li[right:]
    #           
    return merge_result_li


if __name__ == '__main__':
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    print("  alist: %s" % alist)
    sorted_alist = merge_sort(alist)
    print("     list ：%s" % sorted_alist)

#     ：
#   alist: [54, 26, 93, 17, 77, 31, 44, 55, 20]
#    = 54  
#    = 26  
#    = 26    = 54  
#    = 93  
#    = 17  
#    = 17    = 93  
#    = 17    = 26    = 54    = 93  
#    = 77  
#    = 31  
#    = 31    = 77  
#    = 44  
#    = 55  
#    = 20  
#    = 20    = 55  
#    = 20    = 44    = 55  
#    = 20    = 31    = 44    = 55    = 77  
#      list ：[17, 20, 26, 31, 44, 54, 55, 77, 93]

Num 03->時間の複雑さ
最適時間複雑度:O(nlogn)最悪時間複雑度:O(nlogn)安定性:安定性