Algorithm_Sort_Merge sort

tags: Algorithms Sort python

def merge(left_a, right_a):
    """合併兩個陣列"""
    def _merge():        
        while left_a and right_a:
#             print('_merge:', left_a, right_a)
            # 比較兩個陣列的第一個索引的值那一個比較小就優先回傳    
            yield (left_a if left_a[0] < right_a[0] else right_a).pop(0)
        yield from left_a
        yield from right_a
    return list(_merge())
        
def divide(input_array):
    """分割陣列"""
    # 取上高斯點做為中點切掉兩個陣列
    divide_point = len(input_array) // 2
    left_a = input_array[: divide_point]
    right_a = input_array[divide_point: ]
    return left_a, right_a  
    
def merge_sort(input_array):
    """利用遞迴呼執行分割、合併、排序"""
#     print('merge_sort_array:', input_array)
    if len(input_array) == 1:
#         print('return array:', input_array)
        return input_array
    left_a, right_a = divide(input_array)
    return merge(merge_sort(left_a), merge_sort(right_a))
    

下面給出五個資料集在不同資料量下的結果，其中

• l1: 已經排序好的，由小到大
• l2: 已經排序好的，但是逆排序，由大到小
• l3: 亂數生成
• l4: 亂數生成
• l5: 亂數生成

Merge Sort	20000	40000	60000	80000	100000
l1	261 ms	585 ms	805 ms	1.35 s	2.18 s
l2	199 ms	528 ms	880 ms	1.47 s	2.09 s
l3	294 ms	844 ms	1.52 s	2.37 s	3.64 s
l4	282 ms	761 ms	1.45 s	2.39 s	3.42 s
l5	331 ms	735 ms	1.5 s	2.27 s	3.48 s