pythonでの集計ソート

https://www.bilibili.com/video/av17888875?from=search&seid=17019827770934522690 
集計ソートアルゴリズムの時間的複雑度:O(Nlogn)
集計ソートアルゴリズムを用いてN規模のリストをソートするのに要する時間をT(N)とすると、集計ソートアルゴリズムを用いた詳細は、長さNのリストを長さN/2のリスト2つに分割し、それぞれ集計ソートアルゴリズムを用いてソートすると消費時間2*T(N/2)となり、さらに2つの並べ替えられた秩序化されたサブシーケンスを並べ替え(merge)、並べ替えの過程は絶えず比較して消去し、2つの長さN/2のリストを並べ替えるのに要する時間の複雑さは2つのサブリストの要素の個数NがO(N)であることに等しく、最終的に並べ替えられたリストを得る.
計算の複雑さの繰返し式は次のとおりです.
T(N)=2*T(N/2)+O(N)
T(N)=O(Nlog(N))

'''
python          (    )
'''

def merge_sort(array):
    # print(array)
    n=len(array)
    if n==1:
        return array
    mid=n//2
    left=merge_sort(array[:mid])
    right=merge_sort(array[mid:])
    return merge(left,right)
def merge(left,right):
    out=[]
    while left and right:
        p1=left[0]
        p2=right[0]
        if p1<=p2:
            out.append(left.pop(0))
        else:
            out.append(right.pop(0))
    if left:
        out.extend(left)
        #  ，  left             ，  extend              out   
        #    out.append(left)
        #     out+=left
    if right:
        out.extend(right)
    return out
if __name__=='__main__':
    a=[54,26,93,17,77,31,44,55,20]
    assert merge_sort(a)==sorted(a)
    print(merge_sort(a))
    '''
    https://www.bilibili.com/video/av17888875/?p=2
           /         ：             ，     ，              
             ：(    merge_sort     ，              )
    merge_sort([54,26,93,17,77,31,44,55,20])
        mid=4
        left=merge_sort([54,26,93,17])#       ，     
            mid=2
            left=merge_sort([54,26])#       
                mid=1
                left=merge_sort([54])
                    n=1
                    return [54]
                left=[54]#       ，          
                right=merge_sort([26])
                    n=1
                    return [26]
                right=[26]#     
                              （                        ）
                merge(left,right)=[26,54],       
            left=[26,54]    
            right=merge_sort([93,17])  
                mid=1
                left=merge_sort([93])
                    n=1
                    return [93]
                   left=[93]
                right=merge_sort([17])
                    n=1
                    return [17]
                   right=17
                merge([93],[17])
                   [17,93]
               right=[17,93]
            merge(left=[26,54],right=[17,93]) 
                [17,26,54,93]       
           left=[17,26,54,93]
                    
        right=merge_sort([77,31,44,55,20])
              ，     
        right=[20,31,44,55,77]
           left=[17,26,54,93] right=[20,31,44,55,77]  
          [17, 20, 26, 31, 44, 54, 55, 77, 93]
       [17, 20, 26, 31, 44, 54, 55, 77, 93]
            
                        
    
    '''