Python實現歸并排序算法

歸并排序1945年由約翰·馮·諾伊曼首次提出。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用，且各層分治遞歸可以同時進行。

分治法的基本思想

將原問題分解為若干個規模更小但結構與原問題相似的子問題。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解。

歸并排序的基本思想

排序一個數組，我們先把數組從中間分成前后兩部分，然后對前后兩部分分別排序，再將排好序的兩部分合并在一起，這樣整個數組就都有序了。

動畫

（請在發表文章時插入 ms.webp 這張圖片）

代碼實現

```python

def merge(left, right):

'''合并和排序'''

i = 0

j = 0

result = []

length_left = len(left)

length_right = len(right)

while i < length_left and j < length_right:

# 逐個比較兩個列表的元素

# 小的添加進新列表，大的留下繼續比較

if left[i] <= right[j]:

result.append(left[i])

i += 1

else :

result.append(right[j])

j += 1

# 最后加上未比較的元素

result.extend(left[i:])

result.extend(right[j:])

return result

def merge_sort(lists):

'''歸并排序入口，拆分列表'''

# 遞歸退出條件判斷

length = len(lists)

if length <= 1 :

return lists

# 遞歸拆分，取整，兼容py3

mid = length // 2

left = merge_sort(lists[:mid])

right = merge_sort(lists[mid:])

# 合并排序（歸并排序）

return merge(left, right)

numbers = [ 4 , 0 , 7 , 9 , 2 , 8 , 1 , 3 , 6 , 5 ]

assert merge_sort(numbers) == [ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ]

```