合併排序

8.1 什麼是合併排序

合併排序 (Merge Sort) 是一種有效且穩定的比較排序算法，採用"分治法"來排序元素。算法將數組分成兩半，遞歸地排序每一半，然後將已排序的兩半合併成一個已排序的數組。

運作原理：

分割：

• 將原數組分成兩個子數組。
• 對每個子數組重複該過程，直到每個子數組成為單個元素的數組（或為空）。

合併：

• 合併兩個相鄰的子數組為一個已排序的數組。
• 重複合併過程，直到得到一個已排序的數組。

合併排序的時間和空間複雜度

時間複雜度：

• 最壞情況：O(n log n)
• 平均情況：O(n log n)
• 最好情況：O(n log n)

空間複雜度：

O(n) — 需要額外的內存來存儲臨時子數組。

8.2 自頂向下的合併方法

原始序列遞歸地分成兩半，直到得到每個子序列為1個元素。從得到的子序列中用合併法形成已排序的對，然後是已排序的四個元素，依此類推。

讓我們看看這個序列：

將序列分成兩半（遞歸地，直到得到一對）。

用合併法對每個子序列進行排序，並得到最終的序列。

8.3 合併排序算法的實現

這裡我們就需要用到遞歸了！這是一個相當好且快速的算法，跟之前的算法相比起來。它將數組一分為二，分別排序兩個部分，然後快速地合併這兩個已排序的部分。

它的實現看起來大概是這樣的：

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # 找到數組的中間
        left_half = arr[:mid]  # 將數組分為兩個子數組
        right_half = arr[mid:]
        
        merge_sort(left_half)  # 遞歸地排序左半部分
        merge_sort(right_half)  # 遞歸地排序右半部分
        
        i = j = k = 0
        
        # 合併已排序的兩半
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1
        
        # 檢查剩餘元素
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1
        
        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1
    return arr

# 使用範例：
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("已排序數組:", sorted_arr)
# 輸出: 已排序數組: [3, 9, 10, 27, 38, 43, 82]

一開始的關鍵點在於：

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # 找到數組的中間
        left_half = arr[:mid]  # 將數組分為兩個子數組
        right_half = arr[mid:]
        
        merge_sort(left_half)  # 遞歸地排序左半部分
        merge_sort(right_half)  # 遞歸地排序右半部分

這裡發生的事情是：

1. 我們找到數組的中間
2. 將數組分為兩部分
3. 分別對每部分進行排序

這種方法大大加快了算法速度。