如何使用歸并排序

# 如何使用歸并排序

歸并排序（Merge Sort）是一種基于分治思想的高效排序算法，由約翰·馮·諾伊曼于1945年首次提出。其時間復雜度為O(n log n)，在數據量較大時表現優異。本文將詳細介紹歸并排序的原理、實現步驟、代碼示例以及優化技巧。

---

## 目錄
1. [算法原理](#算法原理)
2. [分步驟詳解](#分步驟詳解)
3. [代碼實現](#代碼實現)
4. [復雜度分析](#復雜度分析)
5. [優化策略](#優化策略)
6. [應用場景](#應用場景)
7. [總結](#總結)

---

## 算法原理

歸并排序的核心思想是**分治法**（Divide and Conquer）：
1. **分**：將待排序數組遞歸地分成兩半，直到子數組長度為1。
2. **治**：將兩個已排序的子數組合并為一個有序數組。

合并過程通過比較兩個子數組的元素，按順序放入臨時數組，最后將結果復制回原數組。

---

## 分步驟詳解

### 1. 分割階段
- 將數組從中間分為左右兩部分。
- 對左右子數組遞歸執行分割，直到無法分割（子數組長度為1）。

### 2. 合并階段
- 初始化兩個指針分別指向左右子數組的起始位置。
- 比較指針指向的元素，將較小的元素放入臨時數組，并移動指針。
- 若某一子數組遍歷完畢，直接將另一子數組剩余元素追加到臨時數組。
- 將臨時數組內容復制回原數組對應位置。

---

## 代碼實現

### Python示例
```python
def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]
        
        # 遞歸分割
        merge_sort(left)
        merge_sort(right)
        
        # 合并
        i = j = k = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1
        
        # 處理剩余元素
        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1
        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1

# 測試
arr = [38, 27, 43, 3, 9, 82, 10]
merge_sort(arr)
print("排序后:", arr)

C++示例

#include <vector>
using namespace std;

void merge(vector<int>& arr, int l, int mid, int r) {
    vector<int> temp(r - l + 1);
    int i = l, j = mid + 1, k = 0;
    
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else temp[k++] = arr[j++];
    }
    
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= r) temp[k++] = arr[j++];
    
    for (int p = 0; p < k; p++) {
        arr[l + p] = temp[p];
    }
}

void mergeSort(vector<int>& arr, int l, int r) {
    if (l < r) {
        int mid = l + (r - l) / 2;
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }
}

復雜度分析

優化策略

1. 小數組切換插入排序
   當子數組長度較小時（如≤15），插入排序的實際效率更高。

2. 避免頻繁內存分配
   預分配一個全局臨時數組，減少遞歸中的內存開銷。

3. 非遞歸實現
   使用迭代代替遞歸，防止棧溢出（適用于極大規模數據）。

應用場景

• 大數據排序：如外部排序（海量數據分塊處理）。
• 鏈表排序：歸并排序是鏈表排序的最佳選擇之一。
• 穩定排序需求：如數據庫中對多關鍵字排序。

總結

歸并排序以其穩定的O(n log n)時間復雜度和可并行化的特性，成為經典排序算法之一。盡管需要額外空間，但其在處理大規模數據時的效率優勢顯著。理解其分治思想不僅有助于掌握排序算法，也為解決其他問題（如逆序對統計）提供了思路。

關鍵點回顧：分治法、遞歸分割、有序合并、穩定排序。 “`