【C++教學】排序演算法 5種詳細解說/總整理表格/Best Case/Average Case/Worst Case

這篇文章整理了5種最常見的排序演算法（Sorting Algorithms），詳細解說其運作原理，並且針對Best Case、Average Case、Worst Case詳細分析，最後還有總整理表格！

泡沫排序（Bubble Sort）

原理

冒泡排序是一種簡單的比較排序演算法，透過反覆遍歷陣列，比較相鄰的元素，若順序錯誤（例如前者大於後者）則交換它們。每次遍歷會將最大的（或最小的）元素「冒泡」到正確位置（陣列的尾端或開頭）。這個過程重複進行，直到沒有交換發生，表示陣列已排序。

步驟

1. 從陣列開頭開始，比較相鄰元素，若 arr[j] > arr[j+1]，則交換。
2. 每次遍歷後，最大的元素會被放到陣列尾端（已排序部分）。
3. 重複上述步驟，縮小未排序部分的範圍，直到整個陣列有序。

C++ 程式碼

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false; // 最佳化：追蹤是否發生交換
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break; // 若無交換，表示已排序
    }
}

1. 最佳情形（Best Case）

定義：

• 最佳情形：輸入陣列已經完全排序（例如 [1, 2, 3, 4, 5]）。
• 時間複雜度：O(n)

原因：

• 當陣列已經完全排序時，第一次遍歷（外層迴圈 i=0）的內層迴圈會比較所有相鄰元素，但不會發生任何交換（因為 arr[j] <= arr[j+1] 總是成立）。
• 由於程式碼中有最佳化（swapped 標誌），如果內層迴圈沒有執行任何交換，演算法會提前退出外層迴圈。
• 因此，只需進行一次遍歷（n-1 次比較），總時間複雜度為 O(n)。
• 最佳化的 swapped 標誌是關鍵，否則即使陣列已排序，仍需執行所有遍歷，導致 O(n²)。

例子：

• 輸入：[1, 2, 3, 4, 5]
• 過程：
  • 第一次遍歷（i=0）：比較 (1,2), (2,3), (3,4), (4,5)，無交換，swapped = false。
  • 由於 swapped = false，演算法直接退出。
• 總比較次數：4 次（n-1），無交換。

2. 平均情形（Average Case）

定義：

• 平均情形：輸入陣列元素隨機排列，無特定模式。
• 時間複雜度：O(n²)

原因：

• 在隨機排列的情況下，每次遍歷可能需要多次交換，因為元素並非按順序排列。
• 外層迴圈執行 n-1 次，內層迴圈在第 i 次遍歷時執行 n-i-1 次比較。
• 總比較次數約為 (n-1)+(n-2)+…+1 = n(n-1)/2。
• 交換次數取決於具體數據，但平均約為比較次數的一半（隨機排列下，約有一半的比較導致交換）。
• 由於每次遍歷幾乎都會有交換，無法使用 swapped 標誌提前退出，總時間複雜度為 O(n²)。

例子：

• 輸入：[3, 1, 4, 2, 5]
• 過程：
  • 第一次遍歷（i=0）：比較 (3,1), (3,4), (4,2), (4,5)，交換 (3,1) 和 (4,2)，陣列變為 [1, 3, 2, 4, 5]。
  • 第二次遍歷（i=1）：比較 (1,3), (3,2), (3,4)，交換 (3,2)，陣列變為 [1, 2, 3, 4, 5]。
  • 第三次遍歷（i=2）：比較 (1,2), (2,3)，無交換，提前退出。
• 總比較次數：約 7 次，交換次數：2 次。

3. 最差情形（Worst Case）

定義：

• 最差情形：輸入陣列完全逆序（例如 [5, 4, 3, 2, 1]）。
• 時間複雜度：O(n²)

原因：

• 當陣列完全逆序時，每次遍歷都會觸發最大數量的交換：
  • 第一次遍歷將最大元素（5）移到最後，需要 n-1 次比較和 n-1 次交換。
  • 第二次遍歷將次大元素（4）移到倒數第二，需要 n-2 次比較和 n-2 次交換。
  • 以此類推。
• 總比較次數仍為 n(n−1)/2。
• 交換次數也接近 n(n−1)/2​，因為幾乎每次比較都會導致交換。
• 由於每次遍歷都有交換，無法使用 swapped 標誌提前退出，總時間複雜度為 O(n²)。

例子：

• 輸入：[5, 4, 3, 2, 1]
• 過程：
  • 第一次遍歷（i=0）：比較 (5,4), (5,3), (5,2), (5,1)，交換 4 次，陣列變為 [4, 3, 2, 1, 5]。
  • 第二次遍歷（i=1）：比較 (4,3), (4,2), (4,1)，交換 3 次，陣列變為 [3, 2, 1, 4, 5]。
  • 第三次遍歷（i=2）：比較 (3,2), (3,1)，交換 2 次，陣列變為 [2, 1, 3, 4, 5]。
  • 第四次遍歷（i=3）：比較 (2,1)，交換 1 次，陣列變為 [1, 2, 3, 4, 5]。
  • 第五次遍歷（i=4）：無比較，退出。
• 總比較次數：10 次（n(n-1)/2 = 5*4/2），交換次數：10 次。

實際應用與注意事項

1. 冒泡排序的優點：
   • 簡單易懂，適合初學者。
   • 穩定排序，適合需要保留相等元素順序的場景。
   • 最佳化（swapped 標誌）可顯著提升最佳/近乎有序情況的性能。
2. 冒泡排序的缺點：
   • 效率低（O(n²)），不適合大資料量。
   • 交換次數多，對於交換成本高的資料結構（如大物件）不友好。
3. 適用場景：
   • 小資料量（n < 100）。
   • 陣列近乎有序（接近最佳情形）。
   • 教學或簡單原型設計。

選擇排序（Selection Sort）

原理

選擇排序是一種簡單的比較排序演算法，透過反覆從未排序部分選出最小（或最大）元素，並將其放到已排序部分的開頭。每次迭代保證已排序部分的元素都位於最終正確位置。

步驟：

1. 從未排序部分（初始為整個陣列）找到最小元素的索引。
2. 將最小元素與未排序部分的開頭元素交換。
3. 縮小未排序部分的範圍，重複上述步驟，直到整個陣列有序。

C++ 程式碼：

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        if (minIdx != i) {
            swap(arr[i], arr[minIdx]);
        }
    }
}

特點：

• 不穩定排序（可能改變相等元素的相對順序）。
• 原地排序，空間複雜度 O(1)。
• 交換次數較少（最多 n-1 次），但比較次數固定。

1. 最佳情形（Best Case）

定義：

• 最佳情形：輸入陣列已經完全排序（例如 [1, 2, 3, 4, 5]）。
• 時間複雜度：O(n²)

原因：

• 選擇排序的執行過程不因輸入是否已排序而改變。無論陣列是否有序，每次迭代都需要：
  • 外層迴圈執行 n-1 次（i 從 0 到 n-2）。
  • 內層迴圈掃描未排序部分（j 從 i+1 到 n-1），進行 n-i-1 次比較以找到最小元素。
• 總比較次數為： (n−1)+(n−2)+⋯+1 = n(n−1)/2。
• 在最佳情形下，雖然最小元素總是當前未排序部分的開頭（即 minIdx == i），不會觸發交換，但比較次數不變，因此時間複雜度仍為 O(n²)。
• 與冒泡排序不同，選擇排序沒有提前退出機制（無法像冒泡排序利用 swapped 標誌最佳化）。

例子：

• 輸入：[1, 2, 3, 4, 5]
• 過程：
  • i=0：掃描 [2,3,4,5]，找到最小值 2（索引 1），但 minIdx=0（1 已是最小），無交換。
  • i=1：掃描 [3,4,5]，找到最小值 3（索引 2），無交換。
  • i=2：掃描 [4,5]，找到最小值 4（索引 3），無交換。
  • i=3：掃描 [5]，找到最小值 5（索引 4），無交換。
• 總比較次數：4+3+2+1 = 10 次（n=5），交換次數：0 次。

2. 平均情形（Average Case）

定義：

• 平均情形：輸入陣列元素隨機排列（例如 [3, 1, 4, 2, 5]）。
• 時間複雜度：O(n²)

原因：

• 在隨機排列下，每次迭代仍需掃描未排序部分以找到最小元素，比較次數與最佳情形相同，為 n(n−1)/2。
• 交換次數取決於最小元素的位置，平均約為 O(n)（最多 n-1 次交換）。
• 由於選擇排序的結構固定（無提前退出機制），隨機排列不會顯著改變比較次數，時間複雜度保持 O(n²)。

例子：

• 輸入：[3, 1, 4, 2, 5]
• 過程：
  • i=0：掃描 [1,4,2,5]，找到最小值 1（索引 1），交換 (3,1)，陣列變為 [1, 3, 4, 2, 5]。
  • i=1：掃描 [4,2,5]，找到最小值 2（索引 3），交換 (3,2)，陣列變為 [1, 2, 4, 3, 5]。
  • i=2：掃描 [3,5]，找到最小值 3（索引 3），無交換，陣列仍為 [1, 2, 3, 4, 5]。
  • i=3：掃描 [5]，找到最小值 5（索引 4），無交換。
• 總比較次數：4+3+2+1 = 10 次，交換次數：2 次。

3. 最差情形（Worst Case）

定義：

• 最差情形：輸入陣列完全逆序（例如 [5, 4, 3, 2, 1]）。
• 時間複雜度：O(n²)

原因：

• 當陣列完全逆序時，每次迭代都會找到最小元素在未排序部分的末尾，導致每次迭代都觸發交換：
  • i=0：掃描 [4,3,2,1]，找到最小值 1（索引 4），交換 (5,1)。
  • i=1：掃描 [5,3,2]，找到最小值 2（索引 3），交換 (4,2)。
  • 以此類推。
• 總比較次數仍為 n(n−1)/2。
• 交換次數達到最大值 n-1 次（每次迭代都需交換）。
• 時間複雜度仍為 O(n²)，因為比較次數主導執行時間。

例子：

• 輸入：[5, 4, 3, 2, 1]
• 過程：
  • i=0：掃描 [4,3,2,1]，找到最小值 1（索引 4），交換 (5,1)，陣列變為 [1, 4, 3, 2, 5]。
  • i=1：掃描 [3,2,5]，找到最小值 2（索引 3），交換 (4,2)，陣列變為 [1, 2, 3, 4, 5]。
  • i=2：掃描 [4,5]，找到最小值 3（索引 2），無交換。
  • i=3：掃描 [5]，找到最小值 4（索引 3），無交換。
• 總比較次數：4+3+2+1 = 10 次，交換次數：2 次（實際上逆序交換次數可能隨具體情況略有不同，但最多 n-1 次）。

實際應用與注意事項

1. 選擇排序的優點：
   • 簡單易實現，適合初學者。
   • 交換次數少（最多 n-1 次），適合交換成本高的資料結構（如大物件）。
   • 原地排序，空間需求低（O(1)）。
2. 選擇排序的缺點：
   • 時間複雜度固定為 O(n²)，即使在最佳情形也無法最佳化。
   • 不穩定排序，可能改變相等元素的相對順序。
   • 不適合大資料量或近乎有序的資料（不如插入排序）。
3. 適用場景：
   • 小資料量（n < 100）。
   • 交換成本高（如大物件排序）。
   • 教學或簡單原型設計。

插入排序（Insertion Sort）

原理

插入排序是一種簡單的比較排序演算法，模擬整理撲克牌的過程，將未排序的元素逐一插入到已排序部分的正確位置。每次迭代保證前 i 個元素是有序的。

基本步驟：

1. 從陣列的第二個元素（索引 1）開始，將其視為「當前元素」（key）。
2. 將當前元素與已排序部分的元素（從右到左）比較，若前面的元素大於當前元素，則將前面的元素右移。
3. 找到當前元素的正確位置，將其插入。
4. 重複上述步驟，直到所有元素都被插入到正確位置。

C++ 程式碼：

void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]; // 右移
            j--;
        }
        arr[j + 1] = key; // 插入
    }
}

特點：

• 穩定排序（保留相等元素的相對順序）。
• 原地排序，空間複雜度 O(1)。
• 適合小資料量或部分有序的資料。
• 可在線排序（即時處理新加入的元素）。

1. 最佳情形（Best Case）

定義：

• 最佳情形：輸入陣列已經完全排序（例如 [1, 2, 3, 4, 5]）。
• 時間複雜度：O(n)

原因：

• 當陣列已完全排序時，每次迭代（外層迴圈 i 從 1 到 n-1）只需比較當前元素（key）與前一個元素（arr[j]）。
• 因為陣列已排序，arr[j] <= key 總是成立，內層 while 迴圈不會執行右移操作（僅進行一次比較就退出）。
• 總比較次數為 n-1 次（每個 key 僅比較一次），無右移操作。
• 因此，時間複雜度為 O(n)。

例子：

• 輸入：[1, 2, 3, 4, 5]
• 過程：
  • i=1：key=2，比較 2 與 1，1<2，無右移，直接插入，陣列不變。
  • i=2：key=3，比較 3 與 2，2<3，無右移，直接插入。
  • i=3：key=4，比較 4 與 3，3<4，無右移，直接插入。
  • i=4：key=5，比較 5 與 4，4<5，無右移，直接插入。
• 總比較次數：4 次（n-1），右移次數：0 次。

2. 平均情形（Average Case）

定義：

• 平均情形：輸入陣列元素隨機排列（例如 [3, 1, 4, 2, 5]）。
• 時間複雜度：O(n²)

原因：

• 在隨機排列下，每個元素（key）需要與已排序部分的元素（從右到左）比較，並可能執行多次右移操作。
• 平均而言，key 需要與已排序部分的大約一半元素比較，並右移一半長度的距離。
• 外層迴圈執行 n-1 次，第 i 次迭代的內層迴圈平均比較和右移次數約為 i/2。
• 總比較次數和右移次數均為： 1+2+⋯+(n−1) ≈ n(n−1)/2 ≈ O(n²)。
• 因此，時間複雜度為 O(n²)。

例子：

• 輸入：[3, 1, 4, 2, 5]
• 過程：
  • i=1：key=1，比較 1 與 3，3>1，右移 3，插入 1，陣列變為 [1, 3, 4, 2, 5]。
  • i=2：key=4，比較 4 與 3，3<4，無右移，直接插入，陣列不變。
  • i=3：key=2，比較 2 與 4、3，4>2、3>2，右移 4 和 3，插入 2，陣列變為 [1, 2, 3, 4, 5]。
  • i=4：key=5，比較 5 與 4，4<5，無右移，直接插入。
• 總比較次數：1+1+2+1 = 5 次，右移次數：1+0+2+0 = 3 次。

3. 最差情形（Worst Case）

定義：

• 最差情形：輸入陣列完全逆序（例如 [5, 4, 3, 2, 1]）。
• 時間複雜度：O(n²)

原因：

• 當陣列完全逆序時，每個元素（key）需要與已排序部分的所有元素比較，並將所有元素右移：
  • i=1：key=4，比較並右移 5（1 次）。
  • i=2：key=3，比較並右移 5、4（2 次）。
  • i=3：key=2，比較並右移 5、4、3（3 次）。
  • i=4：key=1，比較並右移 5、4、3、2（4 次）。
• 總比較次數和右移次數均為： 1+2+⋯+(n−1) ≈ n(n−1)/2 ≈ O(n²)。
• 時間複雜度為 O(n²)，因為比較和右移次數均達到最大值。

例子：

• 輸入：[5, 4, 3, 2, 1]
• 過程：
  • i=1：key=4，比較 4 與 5，5>4，右移 5，插入 4，陣列變為 [4, 5, 3, 2, 1]。
  • i=2：key=3，比較 3 與 5、4，5>3、4>3，右移 5、4，插入 3，陣列變為 [3, 4, 5, 2, 1]。
  • i=3：key=2，比較 2 與 5、4、3，右移 5、4、3，插入 2，陣列變為 [2, 3, 4, 5, 1]。
  • i=4：key=1，比較 1 與 5、4、3、2，右移 5、4、3、2，插入 1，陣列變為 [1, 2, 3, 4, 5]。
• 總比較次數：1+2+3+4 = 10 次，右移次數：1+2+3+4 = 10 次。

實際應用與注意事項

1. 插入排序的優點：
   • 簡單易實現，適合初學者。
   • 穩定排序，保留相等元素順序。
   • 在小資料量或部分有序資料上表現優異（接近 O(n)）。
   • 支援在線排序，適合即時插入新元素。
2. 插入排序的缺點：
   • 平均和最差情形為 O(n²)，不適合大資料量。
   • 對於完全無序的大陣列，效率低於快速排序或合併排序。
3. 適用場景：
   • 小資料量（n < 100）。
   • 近乎有序的資料（例如只有少數元素錯位）。
   • 在線排序（即時處理新資料）。

快速排序（Quick Sort）

原理

快速排序是一種高效的分治排序演算法，透過選擇一個基準（pivot），將陣列分為小於基準和等於/大於基準的兩個子陣列，然後遞迴地對子陣列排序。

基本步驟：

1. 選擇一個基準（pivot，通常選第一個、最後一個、中間或隨機元素）。
2. 分割（partition）：重新排列陣列，使小於基準的元素在左邊，等於/大於基準的元素在右邊，返回基準的最終位置。
3. 遞迴：對基準左邊和右邊的子陣列分別進行快速排序。
4. 重複直到子陣列大小為 0 或 1（已排序）。

C++ 程式碼（以最後一個元素作為pivot）：

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        // 分割
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr[i], arr[j]);
            }
        }
        swap(arr[i + 1], arr[high]);
        int pi = i + 1;

        // 遞迴排序子陣列
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

特點：

• 不穩定排序（可能改變相等元素的相對順序）。
• 原地排序，空間複雜度 O(log n)（遞迴堆疊）。
• 基準選擇對性能影響顯著（隨機化或三數取中可改善）。
• 快速排序是 C++ std::sort 的核心演算法之一。

1. 最佳情形（Best Case）

定義：

• 最佳情形：每次分割都能將陣列均分成兩個大小相等的子陣列（例如，基準每次都是中位數）。
• 時間複雜度：O(n log n)

原因：

• 在最佳情形下，基準將陣列均分為兩個大小約為 n/2 的子陣列。
• 分割過程需要 O(n) 次比較（遍歷陣列進行比較和交換）。
• 遞迴深度為 O(log n)，因為陣列每次均分，分割層數約為 log₂(n)。
• 總時間複雜度為： 每層比較次數 O(n)×層數 O(log n)=O(n log⁡ n)。
• 交換次數通常少於比較次數，平均約為 O(n log n)。

例子：

• 輸入：[3, 1, 4, 2, 5]，假設基準選擇總是中位數（例如使用三數取中）。
• 過程（簡化）：
  • 第一次分割：選擇基準 3，分為 [1, 2] 和 [4, 5]，陣列變為 [1, 2, 3, 4, 5]。
  • 左子陣列 [1, 2]：選擇基準 1，分為 [] 和 [2]，已排序。
  • 右子陣列 [4, 5]：選擇基準 4，分為 [] 和 [5]，已排序。
• 總比較次數：約 O(n log n)，例如 n=5 時，分割層數約為 log₂(5) ≈ 2.32，總比較次數約 10~15 次（視基準選擇而定）。

2. 平均情形（Average Case）

定義：

• 平均情形：輸入陣列元素隨機排列，基準選擇隨機或接近隨機。
• 時間複雜度：O(n log n)

原因：

• 在隨機排列下，基準的選擇（即使不是中位數）平均會將陣列分為兩個大小不完全均等的子陣列，但分割比例通常不會極端失衡。
• 平均遞迴深度仍為 O(log n)，因為隨機基準的期望分割比例接近常數（如 1:3 或 1:2）。
• 每層分割需要 O(n) 次比較，總時間複雜度為： 每層 O(n)×平均層數 O(log n)=O(n log⁡ n)。
• 交換次數約為 O(n log n)，具體取決於資料分佈。

例子：

• 輸入：[3, 1, 4, 2, 5]，基準選最後一個元素。
• 過程：
  • 第一次分割：基準 5，分為 [3, 1, 4, 2] 和 []，陣列變為 [3, 1, 4, 2, 5]。
  • 左子陣列 [3, 1, 4, 2]：基準 2，分為 [1] 和 [3, 4]，陣列變為 [1, 2, 3, 4, 5]。
  • 右子陣列 [3, 4]：基準 4，分為 [] 和 [3]，已排序。
• 總比較次數：約 10~15 次（視基準選擇），接近 O(n log n)。

3. 最差情形（Worst Case）

定義：

• 最差情形：每次分割極度不平衡，例如陣列已排序或完全逆序，且基準選第一個或最後一個元素。
• 時間複雜度：O(n²)

原因：

• 在最差情形下，基準總是選到最小或最大元素，導致分割結果為一個子陣列大小為 n-1，另一個為 0。
• 遞迴深度變為 O(n)，每層分割仍需 O(n) 次比較。
• 總時間複雜度為： 每層 O(n)×層數 O(n)=O(n²)。
• 交換次數也接近 O(n²)，因為每次分割可能涉及大量交換。
• 常見於：
  • 陣列已排序（例如 [1, 2, 3, 4, 5]）且基準選最後一個元素。
  • 陣列完全逆序（例如 [5, 4, 3, 2, 1]）。
  • 陣列所有元素相等（例如 [3, 3, 3, 3, 3]）。

例子：

• 輸入：[1, 2, 3, 4, 5]，基準選最後一個元素。
• 過程：
  • 第一次分割：基準 5，分為 [1, 2, 3, 4] 和 []，陣列不變。
  • 第二次分割：基準 4，分為 [1, 2, 3] 和 []，陣列不變。
  • 第三次分割：基準 3，分為 [1, 2] 和 []，陣列不變。
  • 以此類推，遞迴深度為 n。
• 總比較次數：1+2+3+4 = 10 次（n(n-1)/2），交換次數：0 次（因已排序）。

實際應用與注意事項

1. 快速排序的優點：
   • 平均效率高（O(n log n)），適合大資料量。
   • 原地排序，空間需求低（僅遞迴堆疊 O(log n)）。
   • 是 C++ std::sort 的基礎，實務中廣泛應用。
2. 快速排序的缺點：
   • 不穩定排序，可能改變相等元素順序。
   • 最差情形效率低（O(n²)），需小心基準選擇。
   • 遞迴深度可能導致堆疊溢出（可用尾遞迴最佳化）。
3. 適用場景：
   • 大資料量（n > 1000）。
   • 通用排序需求（不要求穩定性）。
   • 記憶體受限但資料量大的情況。

合併排序（Merge Sort）

原理

合併排序是一種基於分治法的穩定排序演算法，透過將陣列分成兩個子陣列，遞迴排序子陣列，然後合併成一個有序陣列。它特別適合鏈結串列和需要穩定排序的場景。

基本步驟：

1. 分割：將陣列分成兩個大小相近的子陣列（通常以中點分割）。
2. 遞迴排序：對兩個子陣列分別進行合併排序，直到子陣列大小為 1（已排序）。
3. 合併：將兩個有序子陣列合併成一個有序陣列，確保穩定性。

C++ 程式碼：

void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    vector<int> L(n1), R(n2);

    // 複製資料到臨時陣列
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];

    // 合併回原陣列
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

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

特點：

• 穩定排序（保留相等元素的相對順序）。
• 非原地排序，空間複雜度 O(n)（需要臨時陣列進行合併）。
• 時間複雜度穩定，不受輸入資料分佈影響。
• 特別適合鏈結串列排序（無需額外空間分配）。

1. 最佳情形（Best Case）

定義：

• 最佳情形：輸入陣列已經完全排序（例如 [1, 2, 3, 4, 5]）。
• 時間複雜度：O(n log n)

原因：

• 合併排序的執行過程不受輸入資料分佈影響，因為它總是將陣列均分為兩個子陣列，遞迴深度固定為 O(log n)。
• 每層遞迴的合併操作需要 O(n) 次比較和移動（將元素從臨時陣列複製回原陣列）。
• 總時間複雜度為： 每層 O(n)×層數 O(log n)=O(n log⁡ n)。
• 在最佳情形下，雖然陣列已排序，但合併過程仍需比較所有元素（因為無法提前判斷子陣列是否有序），因此時間複雜度不變。
• 比較次數和移動次數固定，無最佳化空間。

例子：

• 輸入：[1, 2, 3, 4, 5]
• 過程：
  • 分割：分為 [1, 2] 和 [3, 4, 5]。
  • 左子陣列 [1, 2]：分為 [1] 和 [2]，合併為 [1, 2]（2 次比較）。
  • 右子陣列 [3, 4, 5]：分為 [3] 和 [4, 5]，[4, 5] 分為 [4] 和 [5]，合併為 [4, 5]（2 次比較），再合併為 [3, 4, 5]（3 次比較）。
  • 合併 [1, 2] 和 [3, 4, 5]：比較 5 次，得到 [1, 2, 3, 4, 5]。
• 總比較次數：約 2 + 2 + 3 + 5 = 12 次（n=5，近似 n log n ≈ 5 * log₂(5) ≈ 11.6）。

2. 平均情形（Average Case）

定義：

• 平均情形：輸入陣列元素隨機排列（例如 [3, 1, 4, 2, 5]）。
• 時間複雜度：O(n log n)

原因：

• 合併排序的分割過程固定（總是均分），不受輸入資料分佈影響。
• 遞迴深度為 O(log n)，每層合併需要 O(n) 次比較和移動。
• 總時間複雜度為 O(n log n)，與最佳情形相同。
• 隨機排列可能改變比較的具體結果（例如，左右子陣列的元素交錯合併），但總比較次數仍接近 n log n。
• 移動次數（將元素寫回原陣列）固定為 O(n log n)。

例子：

• 輸入：[3, 1, 4, 2, 5]
• 過程：
  • 分割：分為 [3, 1] 和 [4, 2, 5]。
  • 左子陣列 [3, 1]：分為 [3] 和 [1]，合併為 [1, 3]（2 次比較）。
  • 右子陣列 [4, 2, 5]：分為 [4] 和 [2, 5]，[2, 5] 分為 [2] 和 [5]，合併為 [2, 5]（2 次比較），再合併為 [2, 4, 5]（3 次比較）。
  • 合併 [1, 3] 和 [2, 4, 5]：比較 5 次，得到 [1, 2, 3, 4, 5]。
• 總比較次數：約 2 + 2 + 3 + 5 = 12 次（近似 n log n）。

3. 最差情形（Worst Case）

定義：

• 最差情形：輸入陣列完全逆序（例如 [5, 4, 3, 2, 1]）或所有元素相等（例如 [3, 3, 3, 3, 3]）。
• 時間複雜度：O(n log n)

原因：

• 合併排序的分割和合併過程與輸入資料無關，總是均分陣列，遞迴深度為 O(log n)。
• 每層合併需要 O(n) 次比較和移動，即使陣列逆序或元素相等，比較次數不變（因為穩定排序使用 <=）。
• 總時間複雜度為 O(n log n)，與最佳和平均情形相同。
• 逆序可能導致合併時左右子陣列的元素交錯更多，但總比較次數仍接近 n log n。

例子：

• 輸入：[5, 4, 3, 2, 1]
• 過程：
  • 分割：分為 [5, 4] 和 [3, 2, 1]。
  • 左子陣列 [5, 4]：分為 [5] 和 [4]，合併為 [4, 5]（2 次比較）。
  • 右子陣列 [3, 2, 1]：分為 [3] 和 [2, 1]，[2, 1] 分為 [2] 和 [1]，合併為 [1, 2]（2 次比較），再合併為 [1, 2, 3]（3 次比較）。
  • 合併 [4, 5] 和 [1, 2, 3]：比較 5 次，得到 [1, 2, 3, 4, 5]。
• 總比較次數：約 2 + 2 + 3 + 5 = 12 次（近似 n log n）。

實際應用與注意事項

1. 合併排序的優點：
   • 穩定排序，適合需要保留相等元素順序的場景。
   • 時間複雜度穩定，不受輸入資料影響。
   • 非常適合鏈結串列排序（無需額外分配陣列空間）。
   • 適合外部排序（例如磁碟資料排序）。
2. 合併排序的缺點：
   • 需要 O(n) 額外空間，不適合記憶體受限環境。
   • 對於小資料量，效率不如插入排序（因遞迴和合併開銷）。
3. 適用場景：
   • 大資料量（n > 1000）且需要穩定排序。
   • 鏈結串列排序。
   • 外部排序（如處理大檔案）。

5種排序演算法比較總表格

特性	泡沫排序 Bubble Sort	選擇排序 Selection Sort	插入排序 Insertion Sort	快速排序 Quick Sort	合併排序 Merge Sort
時間複雜度 Best Case	O(n)	O(n²)	O(n)	O(n log n)	O(n log n)
時間複雜度 Average Case	O(n²)	O(n²)	O(n²)	O(n log n)	O(n log n)
時間複雜度 Worst Case	O(n²)	O(n²)	O(n²)	O(n²)	O(n log n)
穩定性	穩定	不穩定	穩定	不穩定	穩定
空間複雜度	O(1)	O(1)	O(1)	O(log n)	O(n)