# 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 |