看了下歸并排序耙箍，總體來說思想很簡單贮庞，實現起來也不是很難。
原理
用圖說明就好啦究西，歸并排序是基于分而治之的思想窗慎，主要分為兩步，一步是“分”卤材，另一步是“治”遮斥，就是將要排序的列表不斷地分解，分解到只有一個元素扇丛，然后在進行排序术吗，將排序好的子列表再進行合并。**時間復雜度為O（nlogn）
image.png
image.png
代碼
def merge_sort(a_list):
if len(a_list)<=1:
return a_list
if len(a_list)>1:
mid=len(a_list)//2
left_half=merge_sort(a_list[:mid])
right_half=merge_sort(a_list[mid:])
i=0
j=0
res=[]
while i<len(left_half) and j<len(right_half):
if left_half[i]<right_half[j]:
res.append(left_half[i])
i+=1
else:
res.append(right_half[j])
j+=1
if i<len(left_half):
res+=left_half[i:]
if j<len(right_half):
res+=right_half[j:]
return res
