---

title: 合併排序

---

合併排序

python

概念

簡單來說就是透過遞迴等我們前面學到的東西，不斷的去做切割，再一步一步的比大小後拼湊回去，先從一個對一個，再從兩個對兩個，一值排下去。

範例

將[5, 9, 4, 8, 7]這一段數字進行排序，他順序將會是->[5], [9], [4], [8], [7]->[5, 9], [4, 8], [7]->[4, 5, 8, 9], [7]->[4, 5, 7, 8, 9]: ``` def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))

def merge(left, right): i = 0 j = 0 ans = [] while i < len(left) and j < len(right): if left[i] <= right[j]: ans.append(left[i]) i += 1 else: ans.append(right[j]) j += 1 while i < len(left): ans.append(left[i]) i += 1 while j < len(right): ans.append(right[j]) j += 1 return ans

arr = [5, 9, 4, 8, 7] ``` 排序過程by AI

例題

題目 看起來我們可以直接用合併排序來完成，並且不像氣泡排序依樣會超時: ``` class Solution: def sortArray(self, nums: List[int]) -> List[int]: def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))

    def merge(left, right):
        i = 0
        j = 0
        ans = []
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                ans.append(left[i])
                i += 1
            else:
                ans.append(right[j])
                j += 1
        while i < len(left):
            ans.append(left[i])
            i += 1
        while j < len(right):
            ans.append(right[j])
            j += 1
        return ans
    return merge_sort(nums)

```