"""
Merge_Sort 歸并排序
分治算法Divide and Conquer
時間復雜度：
"""

# 切割數組 的函數
def merge_sort(alist):
 # 如果長度小于等于1 ，不能再分割了
 if len(alist) <= 1:
  return alist

 # 根據列表長度確定拆分的中間位置
 mid_index = len(alist)//2

 # 使用切片實現對列表的切分
 # left_list = alist[:mid_index]
 # right_list = alist[mid_index:]

 # 遞歸調用，無限切割下去
 left_list = merge_sort(alist[:mid_index])
 right_list = merge_sort(alist[mid_index:])
 return merge(left_list, right_list)

# 排序的函數
def merge(left_list, right_list):
 l_index,r_index = 0,0
 merge_list = []
 # 判斷列表里面是否還有元素可以用
 while l_index < len(left_list) and r_index < len(right_list):
  # 哪邊的元素小于另外一邊的的元素就把哪邊的元素加入進去，對應的索引加一
  if left_list[l_index] < right_list[r_index]:
   merge_list.append(left_list[l_index])
   l_index += 1
  else:
   merge_list.append(right_list[r_index])
   r_index += 1
 # 下面的這兩個就是，如果有一個列表全部添加了，另外一個列表直接添加到merge_list里面了
 merge_list += left_list[l_index:]
 merge_list += right_list[r_index:]
 return merge_list

if __name__ == '__main__':
 alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
 print(f'原列表的順序：{alist}')
 alist = merge_sort(alist)
 print(f'選擇排序之后的列表的順序：{alist}')