排序算法詳解筆記

評價維度

運行效率
就地性
穩定性

自適應性：自適應排序能夠利用輸入數據已有的順序信息來減少計算量，達到更優的時間效率。自適應排序算法的最佳時間復雜度通常優于平均時間復雜度。

是否基于比較：基于比較的排序依賴比較運算符（<、=、>）來判斷元素的相對順序，從而排序整個數組，理論最優時間復雜度為 O(nlog?n) 。而非比較排序不使用比較運算符，時間復雜度可達 O(n) ，但其通用性相對較差。

非比較排序可以突破下界

如果都要比較，那比較次數也會影響性能，比較次數少性能就會好一點

比較排序 O(N^2)

選擇排序

選擇排序（selection sort）的工作原理非常簡單：開啟一個循環，每輪從未排序區間選擇最小的元素，將其放到已排序區間的末尾。
設數組的長度為 n 。

初始狀態下，所有元素未排序，即未排序（索引）區間為 [0,n?1] 。
選取區間 [0,n?1] 中的最小元素，將其與索引 0 處的元素交換。完成后，數組前 1 個元素已排序。
選取區間 [1,n?1] 中的最小元素，將其與索引 1 處的元素交換。完成后，數組前 2 個元素已排序。
以此類推。經過 n?1 輪選擇與交換后，數組前 n?1 個元素已排序。
僅剩的一個元素必定是最大元素，無須排序，因此數組排序完成。

/* 選擇排序 */
void selectionSort(vector<int> &nums) {int n = nums.size();// 外循環：未排序區間為 [i, n-1]for (int i = 0; i < n - 1; i++) {// 內循環：找到未排序區間內的最小元素int k = i;for (int j = i + 1; j < n; j++) {if (nums[j] < nums[k])k = j; // 記錄最小元素的索引}// 將該最小元素與未排序區間的首個元素交換swap(nums[i], nums[k]);}
}

時間復雜度為 O(n^2)、非自適應排序：外循環共 n?1 輪，第一輪的未排序區間長度為 n ，最后一輪的未排序區間長度為 2 ，即各輪外循環分別包含 n、n?1、…、3、2 輪內循環，求和為 (n?1)(n+2) 。
空間復雜度為 O(1)、==原地排序==：指針 i 和 j 使用常數大小的額外空間。
非穩定排序：如下圖所示，元素 nums[i] 有可能被交換至與其相等的元素的右邊，導致兩者的相對順序發生改變。

冒泡排序 O(N^2)

冒泡排序（bubble sort）通過連續地比較與交換相鄰元素實現排序。這個過程就像氣泡從底部升到頂部一樣，因此得名冒泡排序。
冒泡過程可以利用元素交換操作來模擬：從數組最左端開始向右遍歷，依次比較相鄰元素大小，如果“左元素 > 右元素”就交換二者。遍歷完成后，最大的元素會被移動到數組的最右端。
設數組的長度為 n ，冒泡排序的步驟如圖所示。

首先，對 n 個元素執行“冒泡”，將數組的最大元素交換至正確位置。
接下來，對剩余 n?1 個元素執行“冒泡”，將第二大元素交換至正確位置。
以此類推，經過 n?1 輪“冒泡”后，前 n?1 大的元素都被交換至正確位置。
僅剩的一個元素必定是最小元素，無須排序，因此數組排序完成。

void bubbleSort(vector<int> &nums){for(int i = nums.size()-1;i>0;i++){for(int j = 0;j<i;j++){if(nums[j]>nums[j+1]){swap(nums[j],nums[j+1]);}}}
}

引入flag優化

引入flag 優化
經過優化，冒泡排序的最差時間復雜度和平均時間復雜度仍為 𝑂(𝑛2) ；但當輸入數組完全有序時，可達到最佳時間復雜度 𝑂(𝑛) 。

/* 冒泡排序（標志優化）*/
void bubbleSortWithFlag(vector<int> &nums) {// 外循環：未排序區間為 [0, i]for (int i = nums.size() - 1; i > 0; i--) {bool flag = false; // 初始化標志位// 內循環：將未排序區間 [0, i] 中的最大元素交換至該區間的最右端for (int j = 0; j < i; j++) {if (nums[j] > nums[j + 1]) {// 交換 nums[j] 與 nums[j + 1]// 這里使用了 std::swap() 函數swap(nums[j], nums[j + 1]);flag = true; // 記錄交換元素}}if (!flag)break; // 此輪“冒泡”未交換任何元素，直接跳出}
}

時間復雜度為 O(n2)、自適應排序：各輪“冒泡”遍歷的數組長度依次為 n?1、n?2、…、2、1 ，總和為 (n?1)n/2 。在引入 flag 優化后，最佳時間復雜度可達到 O(n) 。
空間復雜度為 O(1)、原地排序：指針 i 和 j 使用常數大小的額外空間。
穩定排序：由于在“冒泡”中遇到相等元素不交換。

插入排序 O(N^2)

插入排序的整體流程。

初始狀態下，數組的第 1 個元素已完成排序。
選取數組的第 2 個元素作為 base ，將其插入到正確位置后，數組的前 2 個元素已排序。
選取第 3 個元素作為 base ，將其插入到正確位置后，數組的前 3 個元素已排序。
以此類推，在最后一輪中，選取最后一個元素作為 base ，將其插入到正確位置后，所有元素均已排序。

/* 插入排序 */
void insertionSort(vector<int> &nums) {// 外循環：已排序區間為 [0, i-1]for (int i = 1;i<nums.size();i++) {int base = nums[i],j = i-1;// 內循環：將 base 插入到已排序區間 [0, i-1] 中的正確位置while (j>=0&&nums[j]>base) {nums[j+1] = nums[j];j--;}// 將 base 賦值到正確位置nums[j+1] = base;}
}

時間復雜度為 O(n2)、自適應排序：在最差情況下，每次插入操作分別需要循環 n?1、n?2、…、2、1 次，求和得到 (n?1)n/2 ，因此時間復雜度為 O(n2) 。在遇到有序數據時，插入操作會提前終止。當輸入數組完全有序時，插入排序達到最佳時間復雜度 O(n) 。
空間復雜度為 O(1)、原地排序：指針 i 和 j 使用常數大小的額外空間。
穩定排序：在插入操作過程中，我們會將元素插入到相等元素的右側，不會改變它們的順序。

優勢

插入排序的時間復雜度為 O(n2) ，而我們即將學習的快速排序的時間復雜度為 O(nlog?n) 。盡管插入排序的時間復雜度更高，但在數據量較小的情況下，插入排序通常更快。
這個結論與線性查找和二分查找的適用情況的結論類似。快速排序這類 O(nlog?n) 的算法屬于基于分治策略的排序算法，往往包含更多單元計算操作。而在數據量較小時，n2 和 nlog?n 的數值比較接近，復雜度不占主導地位，每輪中的單元操作數量起到決定性作用。

實際上，許多編程語言（例如 Java）的內置排序函數采用了插入排序，大致思路為：對于長數組，采用基于分治策略的排序算法，例如快速排序；對于短數組，直接使用插入排序。如下圖所示。

/**  * Tuning parameter: list size at or below which insertion sort will be * used in preference to mergesort. * To be removed in a future release. */private static final int INSERTIONSORT_THRESHOLD = 7;  /**  * Src is the source array that starts at index 0 * Dest is the (possibly larger) array destination with a possible offset * low is the index in dest to start sorting * high is the end index in dest to end sorting * off is the offset to generate corresponding low, high in src * To be removed in a future release. */@SuppressWarnings({"unchecked", "rawtypes"})  
private static void mergeSort(Object[] src,  Object[] dest,  int low,  int high,  int off) {  int length = high - low;  // Insertion sort on smallest arrays  if (length < INSERTIONSORT_THRESHOLD) {  for (int i=low; i<high; i++)  for (int j=i; j>low &&  ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)  swap(dest, j, j-1);  return;  }  // Recursively sort halves of dest into src  int destLow  = low;  int destHigh = high;  low  += off;  high += off;  int mid = (low + high) >>> 1;  mergeSort(dest, src, low, mid, -off);  mergeSort(dest, src, mid, high, -off);  // If list is already sorted, just copy from src to dest.  This is an  // optimization that results in faster sorts for nearly ordered lists.    if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {  System.arraycopy(src, low, dest, destLow, length);  return;  }  // Merge sorted halves (now in src) into dest  for(int i = destLow, p = low, q = mid; i < destHigh; i++) {  if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)  dest[i] = src[p++];  else  dest[i] = src[q++];  }  
}

雖然冒泡排序、選擇排序和插入排序的時間復雜度都為 O(n2) ，但在實際情況中，插入排序的使用頻率顯著高于冒泡排序和選擇排序，主要有以下原因。

冒泡排序基于元素交換實現，需要借助一個臨時變量，共涉及 3 個單元操作；插入排序基于元素賦值實現，僅需 1 個單元操作。因此，冒泡排序的計算開銷通常比插入排序更高。
選擇排序在任何情況下的時間復雜度都為 O(n2) 。如果給定一組部分有序的數據，插入排序通常比選擇排序效率更高。
選擇排序不穩定，無法應用于多級排序。

快速排序 O(NlogN)

快速排序（quick sort）是一種基于分治策略的排序算法，運行高效，應用廣泛。

快速排序的核心操作是“哨兵劃分”，其目標是：選擇數組中的某個元素作為“基準數”，將所有小于基準數的元素移到其左側，而大于基準數的元素移到其右側。具體來說，哨兵劃分的流程。

選取數組最左端元素作為基準數，初始化兩個指針 i 和 j 分別指向數組的兩端。
設置一個循環，在每輪中使用 i（j）分別尋找第一個比基準數大（小）的元素，然后交換這兩個元素。
循環執行步驟 2. ，直到 i 和 j 相遇時停止，最后將基準數交換至兩個子數組的分界線。

/* 哨兵劃分 */
int partition(vector<int> &nums, int left, int right) {// 以 nums[left] 為基準數int i = left, j = right;while (i < j) {while (i < j && nums[j] >= nums[left])j--;                // 從右向左找首個小于基準數的元素while (i < j && nums[i] <= nums[left])i++;                // 從左向右找首個大于基準數的元素swap(nums[i], nums[j]); // 交換這兩個元素}swap(nums[i], nums[left]);  // 將基準數交換至兩子數組的分界線return i;                   // 返回基準數的索引
}
/* 快速排序 */
void quickSort(vector<int> &nums, int left, int right) {// 子數組長度為 1 時終止遞歸if (left >= right)return;// 哨兵劃分int pivot = partition(nums, left, right);// 遞歸左子數組、右子數組quickSort(nums, left, pivot - 1);quickSort(nums, pivot + 1, right);
}

時間復雜度為 O(nlog?n)、非自適應排序：在平均情況下，哨兵劃分的遞歸層數為 log?n ，每層中的總循環數為 n ，總體使用 O(nlog?n) 時間。在最差情況下，每輪哨兵劃分操作都將長度為 n 的數組劃分為長度為 0 和 n?1 的兩個子數組，此時遞歸層數達到 n ，每層中的循環數為 n ，總體使用 O(n2) 時間。
空間復雜度為 O(n)、原地排序：在輸入數組完全倒序的情況下，達到最差遞歸深度 n ，使用 O(n) 棧幀空間。排序操作是在原數組上進行的，未借助額外數組。
非穩定排序：在哨兵劃分的最后一步，基準數可能會被交換至相等元素的右側。

優化

原始的切分:

對于某個j,a[j]已排定
a[lo]到a[j-1]中的所有袁術都不大于a[j]
a[j+1]到a[hi]中的所有元素都不小于a[j]

對于小數組，快速排序比插入排序慢
因為遞歸，快速排序在小數組中也會調用自己

三取樣切分

/* 選取三個候選元素的中位數 */
int medianThree(vector<int> &nums, int left, int mid, int right) {int l = nums[left], m = nums[mid], r = nums[right];if ((l <= m && m <= r) || (r <= m && m <= l))return mid; // m 在 l 和 r 之間if ((m <= l && l <= r) || (r <= l && l <= m))return left; // l 在 m 和 r 之間return right;
}/* 哨兵劃分（三數取中值） */
int partition(vector<int> &nums, int left, int right) {// 選取三個候選元素的中位數int med = medianThree(nums, left, (left + right) / 2, right);// 將中位數交換至數組最左端swap(nums[left], nums[med]);// 以 nums[left] 為基準數int i = left, j = right;while (i < j) {while (i < j && nums[j] >= nums[left])j--;                // 從右向左找首個小于基準數的元素while (i < j && nums[i] <= nums[left])i++;                // 從左向右找首個大于基準數的元素swap(nums[i], nums[j]); // 交換這兩個元素}swap(nums[i], nums[left]);  // 將基準數交換至兩子數組的分界線return i;                   // 返回基準數的索引
}

遞歸優化

在某些輸入下，快速排序可能占用空間較多。以完全有序的輸入數組為例，設遞歸中的子數組長度為 m ，每輪哨兵劃分操作都將產生長度為 0 的左子數組和長度為 m?1 的右子數組，這意味著每一層遞歸調用減少的問題規模非常小（只減少一個元素），遞歸樹的高度會達到 n?1 ，此時需要占用 O(n) 大小的棧幀空間。

為了防止棧幀空間的累積，我們可以在每輪哨兵排序完成后，比較兩個子數組的長度，僅對較短的子數組進行遞歸。由于較短子數組的長度不會超過 n/2 ，因此這種方法能確保遞歸深度不超過 log?n ，從而將最差空間復雜度優化至 O(log?n) 。代碼如下所示

/* 快速排序（尾遞歸優化） */
void quickSort(vector<int> &nums, int left, int right) {// 子數組長度為 1 時終止while (left < right) {// 哨兵劃分操作int pivot = partition(nums, left, right);// 對兩個子數組中較短的那個執行快速排序if (pivot - left < right - pivot) {quickSort(nums, left, pivot - 1); // 遞歸排序左子數組left = pivot + 1;                 // 剩余未排序區間為 [pivot + 1, right]} else {quickSort(nums, pivot + 1, right); // 遞歸排序右子數組right = pivot - 1;                 // 剩余未排序區間為 [left, pivot - 1]}}
}

三向切分

#include <vector>
using namespace std;// 交換函數
template<typename T>
void exch(vector<T>& a, int i, int j) {T temp = a[i];a[i] = a[j];a[j] = temp;
}// 插入排序
template<typename T>
void insertionSort(vector<T>& a, int lo, int hi) {for (int i = lo + 1; i <= hi; i++) {T temp = a[i];int j = i;while (j > lo && a[j-1] > temp) {a[j] = a[j-1];j--;}a[j] = temp;}
}// Bentley-McIlroy三向切分快速排序
template<typename T>
void quickSortBentleyMcIlroy(vector<T>& a, int lo, int hi, int M) {if (hi - lo + 1 <= M) {insertionSort(a, lo, hi);return;}int p = lo;      // p指向等于pivot的左側區域的右邊界+1int q = hi;      // q指向等于pivot的右側區域的左邊界-1int i = lo;      // i指向小于pivot的區域的右邊界+1int j = hi;      // j指向大于pivot的區域的左邊界-1T pivot = a[lo];while (i <= j) {// 處理小于pivot的元素while (i <= j && a[i] <= pivot) {if (a[i] == pivot) {exch(a, p, i);p++;}i++;}// 處理大于pivot的元素while (i <= j && a[j] >= pivot) {if (a[j] == pivot) {exch(a, j, q);q--;}j--;}if (i <= j) {exch(a, i, j);i++;j--;}}// 將左側的等于pivot的元素移到中間int k = lo;while (k < p) {exch(a, k, j);k++;j--;}// 將右側的等于pivot的元素移到中間k = hi;while (k > q) {exch(a, i, k);k--;i++;}// 遞歸排序左右兩部分quickSortBentleyMcIlroy(a, lo, j, M);quickSortBentleyMcIlroy(a, i, hi, M);
}// 排序入口函數
template<typename T>
void sort(vector<T>& a, int M = 10) {quickSortBentleyMcIlroy(a, 0, a.size() - 1, M);
}

實驗驗證

小規模數組 (1000 個元素)

測試類型	普通快速排序	三向切分快速排序	速度比較
隨機數組	0.2322 ms	0.2369 ms	普通快排略快 (1.02×)
重復元素較多 (唯一元素數量: 10)	0.1399 ms	0.0153 ms	三向快排明顯更快 (9.14×)

中等規模數組 (100,000 個元素)

測試類型	普通快速排序	三向切分快速排序	速度比較
隨機數組	4.4053 ms	6.7698 ms	普通快排更快 (1.54×)
重復元素較多 (唯一元素數量: 100)	29.5879 ms	1.8805 ms	三向快排顯著更快 (15.73×)

大規模數組 (1,000,000 個元素)

測試類型	普通快速排序	三向切分快速排序	速度比較
隨機數組	57.8245 ms	64.6942 ms	普通快排略快 (1.12×)
重復元素較多 (唯一元素數量: 1000)	272.8528 ms	31.4603 ms	三向快排極大提升 (8.67×)

結論

隨機數據：普通快速排序在所有規模上都略微快于三向切分快速排序
重復元素較多的數據：三向切分快速排序有巨大優勢，在中等規模數組上最高可達15.73倍性能提升
數據規模影響：隨著數據規模增大，處理重復元素時三向切分方法的優勢愈發明顯
在實際應用中，如果預期數據中重復元素較多，特別是在處理大規模數據時，三向切分快速排序會是更好的選擇。

import java.util.Arrays;
import java.util.Random;public class QuickSortTest {// 普通快速排序public static void quickSort(int[] arr, int low, int high) {if (low < high) {int pivot = partition(arr, low, high);quickSort(arr, low, pivot - 1);quickSort(arr, pivot + 1, high);}}private static int partition(int[] arr, int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] <= pivot) {i++;swap(arr, i, j);}}swap(arr, i + 1, high);return i + 1;}// 三向切分的快速排序public static void quickSort3Way(int[] arr, int low, int high) {if (high <= low) return;int lt = low, i = low + 1, gt = high;int pivot = arr[low];while (i <= gt) {if (arr[i] < pivot) {swap(arr, lt++, i++);} else if (arr[i] > pivot) {swap(arr, i, gt--);} else {i++;}}quickSort3Way(arr, low, lt - 1);quickSort3Way(arr, gt + 1, high);}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}// 生成隨機數組private static int[] generateRandomArray(int size, int maxValue) {Random random = new Random();int[] arr = new int[size];for (int i = 0; i < size; i++) {arr[i] = random.nextInt(maxValue);}return arr;}// 生成有大量重復元素的數組private static int[] generateArrayWithDuplicates(int size, int uniqueCount) {Random random = new Random();int[] arr = new int[size];for (int i = 0; i < size; i++) {arr[i] = random.nextInt(uniqueCount);}return arr;}// 驗證數組是否排序正確private static boolean isSorted(int[] arr) {for (int i = 1; i < arr.length; i++) {if (arr[i - 1] > arr[i]) {return false;}}return true;}// 運行測試private static void runTest(String testName, int size, int maxValue, int uniqueCount) {System.out.println("=== " + testName + " ===");System.out.println("數組大小: " + size);// 測試隨機數組int[] arr1 = generateRandomArray(size, maxValue);int[] arr2 = Arrays.copyOf(arr1, arr1.length);System.out.println("隨機數組測試:");// 測試普通快速排序long startTime = System.nanoTime();quickSort(arr1, 0, arr1.length - 1);long endTime = System.nanoTime();double duration = (endTime - startTime) / 1_000_000.0;System.out.println("普通快速排序時間: " + duration + " ms");System.out.println("排序正確: " + isSorted(arr1));// 測試三向切分快速排序startTime = System.nanoTime();quickSort3Way(arr2, 0, arr2.length - 1);endTime = System.nanoTime();duration = (endTime - startTime) / 1_000_000.0;System.out.println("三向切分快速排序時間: " + duration + " ms");System.out.println("排序正確: " + isSorted(arr2));// 測試大量重復元素的數組int[] arr3 = generateArrayWithDuplicates(size, uniqueCount);int[] arr4 = Arrays.copyOf(arr3, arr3.length);System.out.println("\n重復元素較多的數組測試 (唯一元素數量: " + uniqueCount + "):");// 測試普通快速排序startTime = System.nanoTime();quickSort(arr3, 0, arr3.length - 1);endTime = System.nanoTime();duration = (endTime - startTime) / 1_000_000.0;System.out.println("普通快速排序時間: " + duration + " ms");System.out.println("排序正確: " + isSorted(arr3));// 測試三向切分快速排序startTime = System.nanoTime();quickSort3Way(arr4, 0, arr4.length - 1);endTime = System.nanoTime();duration = (endTime - startTime) / 1_000_000.0;System.out.println("三向切分快速排序時間: " + duration + " ms");System.out.println("排序正確: " + isSorted(arr4));System.out.println();}public static void main(String[] args) {// 測試小規模數組runTest("小規模數組", 1000, 1000, 10);// 測試中等規模數組runTest("中等規模數組", 100000, 100000, 100);// 測試大規模數組runTest("大規模數組", 1000000, 1000000, 1000);}
}

歸并排序 O(NlogN)

“劃分階段”從頂至底遞歸地將數組從中點切分為兩個子數組。

計算數組中點 mid ，遞歸劃分左子數組（區間 [left, mid] ）和右子數組（區間 [mid + 1, right] ）。
遞歸執行步驟 1. ，直至子數組區間長度為 1 時終止。

“合并階段”從底至頂地將左子數組和右子數組合并為一個有序數組。需要注意的是，從長度為 1 的子數組開始合并，合并階段中的每個子數組都是有序的。

觀察發現，歸并排序與二叉樹后序遍歷的遞歸順序是一致的。

后序遍歷：先遞歸左子樹，再遞歸右子樹，最后處理根節點。
歸并排序：先遞歸左子數組，再遞歸右子數組，最后處理合并。

歸并排序的實現如以下代碼所示。請注意，nums 的待合并區間為 [left, right] ，而 tmp 的對應區間為 [0, right - left] 。

/* 合并左子數組和右子數組 */
void merge(vector<int> &nums, int left, int mid, int right) {// 左子數組區間為 [left, mid], 右子數組區間為 [mid+1, right]// 創建一個臨時數組 tmp ，用于存放合并后的結果vector<int> tmp(right - left + 1);// 初始化左子數組和右子數組的起始索引int i = left, j = mid + 1, k = 0;// 當左右子數組都還有元素時，進行比較并將較小的元素復制到臨時數組中while (i <= mid && j <= right) {if (nums[i] <= nums[j])tmp[k++] = nums[i++];elsetmp[k++] = nums[j++];}// 將左子數組和右子數組的剩余元素復制到臨時數組中while (i <= mid) {tmp[k++] = nums[i++];}while (j <= right) {tmp[k++] = nums[j++];}// 將臨時數組 tmp 中的元素復制回原數組 nums 的對應區間for (k = 0; k < tmp.size(); k++) {nums[left + k] = tmp[k];}
}/* 歸并排序 */
void mergeSort(vector<int> &nums, int left, int right) {// 終止條件if (left >= right)return; // 當子數組長度為 1 時終止遞歸// 劃分階段int mid = left + (right - left) / 2;    // 計算中點mergeSort(nums, left, mid);      // 遞歸左子數組mergeSort(nums, mid + 1, right); // 遞歸右子數組// 合并階段merge(nums, left, mid, right);
}

時間復雜度為 O(nlog?n)、非自適應排序：劃分產生高度為 log?n 的遞歸樹，每層合并的總操作數量為 n ，因此總體時間復雜度為 O(nlog?n) 。
空間復雜度為 O(n)、非原地排序：遞歸深度為 log?n ，使用 O(log?n) 大小的棧幀空間。合并操作需要借助輔助數組實現，使用 O(n) 大小的額外空間。
穩定排序：在合并過程中，相等元素的次序保持不變。

對于鏈表，歸并排序相較于其他排序算法具有顯著優勢，可以將鏈表排序任務的空間復雜度優化至 O(1) 。

劃分階段：可以使用“迭代”替代“遞歸”來實現鏈表劃分工作，從而省去遞歸使用的棧幀空間。
合并階段：在鏈表中，節點增刪操作僅需改變引用（指針）即可實現，因此合并階段（將兩個短有序鏈表合并為一個長有序鏈表）無須創建額外鏈表。

#include <iostream>// 定義鏈表節點結構
struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};// 合并兩個有序鏈表，返回合并后的頭指針
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode dummy(0);ListNode* tail = &dummy;while (l1 && l2) {if (l1->val < l2->val) {tail->next = l1;l1 = l1->next;} else {tail->next = l2;l2 = l2->next;}tail = tail->next;}tail->next = l1 ? l1 : l2;return dummy.next;
}// 計算鏈表長度
int getLength(ListNode* head) {int len = 0;while (head) {++len;head = head->next;}return len;
}// 非遞歸自底向上歸并排序
ListNode* mergeSortList(ListNode* head) {if (!head || !head->next) return head;int n = getLength(head);ListNode dummy(0);dummy.next = head;ListNode* left;ListNode* right;ListNode* tail;for (int step = 1; step < n; step <<= 1) {ListNode* curr = dummy.next;tail = &dummy;while (curr) {left = curr;// 劃分左子鏈表int leftSize = step;for (int i = 1; i < leftSize && curr->next; ++i) {curr = curr->next;}right = curr->next;curr->next = nullptr;  // 切斷左鏈表curr = right;// 劃分右子鏈表int rightSize = step;for (int i = 1; i < rightSize && curr && curr->next; ++i) {curr = curr->next;}ListNode* nextSub = nullptr;if (curr) {nextSub = curr->next;curr->next = nullptr;  // 切斷右鏈表}// 合并左右鏈表ListNode* merged = mergeTwoLists(left, right);// 將合并后的部分鏈接回主鏈表tail->next = merged;while (tail->next) tail = tail->next;// 繼續處理剩余部分curr = nextSub;}}return dummy.next;
}// 輔助：打印鏈表
void printList(ListNode* head) {while (head) {std::cout << head->val;if (head->next) std::cout << " -> ";head = head->next;}std::cout << std::endl;
}int main() {// 測試示例ListNode* head = new ListNode(4);head->next = new ListNode(2);head->next->next = new ListNode(1);head->next->next->next = new ListNode(3);head->next->next->next->next = new ListNode(2);std::cout << "排序前: ";printList(head);head = mergeSortList(head);std::cout << "排序后: ";printList(head);return 0;
}

堆排序 O(NlogN)

設數組的長度為 n ，堆排序的流程。

輸入數組并建立大頂堆。完成后，最大元素位于堆頂。
將堆頂元素（第一個元素）與堆底元素（最后一個元素）交換。完成交換后，堆的長度減 1 ，已排序元素數量加 1 。
從堆頂元素開始，從頂到底執行堆化操作（sift down）。完成堆化后，堆的性質得到修復。
循環執行第 2. 步和第 3. 步。循環 n?1 輪后，即可完成數組排序。

/* 堆的長度為 n ，從節點 i 開始，從頂至底堆化 */
void siftDown(vector<int> &nums, int n, int i) {while (true) {// 判斷節點 i, l, r 中值最大的節點，記為 maint l = 2 * i + 1;int r = 2 * i + 2;int ma = i;if (l < n && nums[l] > nums[ma])ma = l;if (r < n && nums[r] > nums[ma])ma = r;// 若節點 i 最大或索引 l, r 越界，則無須繼續堆化，跳出if (ma == i) {break;}// 交換兩節點swap(nums[i], nums[ma]);// 循環向下堆化i = ma;}
}/* 堆排序 */
void heapSort(vector<int> &nums) {// 建堆操作：堆化除葉節點以外的其他所有節點for (int i = nums.size() / 2 - 1; i >= 0; --i) {siftDown(nums, nums.size(), i);}// 從堆中提取最大元素，循環 n-1 輪for (int i = nums.size() - 1; i > 0; --i) {// 交換根節點與最右葉節點（交換首元素與尾元素）swap(nums[0], nums[i]);// 以根節點為起點，從頂至底進行堆化siftDown(nums, i, 0);}
}

時間復雜度為 O(nlog?n)、非自適應排序：建堆操作使用 O(n) 時間。從堆中提取最大元素的時間復雜度為 O(log?n) ，共循環 n?1 輪。
空間復雜度為 O(1)、原地排序：幾個指針變量使用 O(1) 空間。元素交換和堆化操作都是在原數組上進行的。
非穩定排序：在交換堆頂元素和堆底元素時，相等元素的相對位置可能發生變化。

非比較排序

桶排序

考慮一個長度為 n 的數組，其元素是范圍 [0,1) 內的浮點數。桶排序的流程。

初始化 k 個桶，將 n 個元素分配到 k 個桶中。
對每個桶分別執行排序（這里采用編程語言的內置排序函數）。
按照桶從小到大的順序合并結果。

數組元素 num 的取值區間是 [0,1)，所以最簡單直接的映射就是

int idx = static_cast<int>(num * k);

num * k 會把 “0 → k” 這個區間線性映射到 [0, k)，
再取整 (static_cast<int> 或 floor) 就得到合法的桶索引 0…k–1。

為了保險起見（萬一有極小的浮點誤差把 num*k 變成正好等于 k），可以再做一次上界截斷：

int idx = std::min(static_cast<int>(num * k), k - 1);
buckets[idx].push_back(num);

如果輸入范圍不是固定在 [0,1)，而是任意 [minVal, maxVal)，那么對應的映射公式就是

int idx = static_cast<int>((num - minVal) / (maxVal - minVal) * k);
idx = std::min(std::max(idx, 0), k - 1);

這樣就能將任意區間 [minVal, maxVal) 上的數均勻分配到 k 個桶里。

/* 桶排序 */
void bucketSort(vector<float> &nums) {// 初始化 k = n/2 個桶，預期向每個桶分配 2 個元素int k = nums.size() / 2;vector<vector<float>> buckets(k);// 1. 將數組元素分配到各個桶中for (float num : nums) {// 輸入數據范圍為 [0, 1)，使用 num * k 映射到索引范圍 [0, k-1]int i = num * k;// 將 num 添加進桶 bucket_idxbuckets[i].push_back(num);}// 2. 對各個桶執行排序for (vector<float> &bucket : buckets) {// 使用內置排序函數，也可以替換成其他排序算法sort(bucket.begin(), bucket.end());}// 3. 遍歷桶合并結果int i = 0;for (vector<float> &bucket : buckets) {for (float num : bucket) {nums[i++] = num;}}
}

桶排序適用于處理體量很大的數據。例如，輸入數據包含 100 萬個元素，由于空間限制，系統內存無法一次性加載所有數據。此時，可以將數據分成 1000 個桶，然后分別對每個桶進行排序，最后將結果合并。

時間復雜度為 O(n+k) ：假設元素在各個桶內平均分布，那么每個桶內的元素數量為 nk 。假設排序單個桶使用 O(nklog?nk) 時間，則排序所有桶使用 O(nlog?nk) 時間。當桶數量 k 比較大時，時間復雜度則趨向于 O(n) 。合并結果時需要遍歷所有桶和元素，花費 O(n+k) 時間。在最差情況下，所有數據被分配到一個桶中，且排序該桶使用 O(n2) 時間。
空間復雜度為 O(n+k)、非原地排序：需要借助 k 個桶和總共 n 個元素的額外空間。
桶排序是否穩定取決于排序桶內元素的算法是否穩定。

計數排序

計數排序（counting sort）通過統計元素數量來實現排序，通常應用于整數數組。

遍歷數組，找出其中的最大數字，記為 m ，然后創建一個長度為 m+1 的輔助數組 counter 。
借助 counter 統計 nums 中各數字的出現次數，其中 counter[num] 對應數字 num 的出現次數。統計方法很簡單，只需遍歷 nums（設當前數字為 num），每輪將 counter[num] 增加 1 即可。
由于 counter 的各個索引天然有序，因此相當于所有數字已經排序好了。接下來，我們遍歷 counter ，根據各數字出現次數從小到大的順序填入 nums 即可。

/* 計數排序 */
// 簡單實現，無法用于排序對象
void countingSortNaive(vector<int> &nums) {// 1. 統計數組最大元素 mint m = 0;for (int num : nums) {m = max(m, num);}// 2. 統計各數字的出現次數// counter[num] 代表 num 的出現次數vector<int> counter(m + 1, 0);for (int num : nums) {counter[num]++;}// 3. 遍歷 counter ，將各元素填入原數組 numsint i = 0;for (int num = 0; num < m + 1; num++) {for (int j = 0; j < counter[num]; j++, i++) {nums[i] = num;}}
}

時間復雜度為 O(n+m)、非自適應排序 ：涉及遍歷 nums 和遍歷 counter ，都使用線性時間。一般情況下 n?m ，時間復雜度趨于 O(n) 。
空間復雜度為 O(n+m)、非原地排序：借助了長度分別為 n 和 m 的數組 res 和 counter 。
穩定排序：由于向 res 中填充元素的順序是“從右向左”的，因此倒序遍歷 nums 可以避免改變相等元素之間的相對位置，從而實現穩定排序。實際上，正序遍歷 nums 也可以得到正確的排序結果，但結果是非穩定的。

基數排序

以學號數據為例，假設數字的最低位是第 1 位，最高位是第 8 位，基數排序的流程如圖 11-18 所示。

初始化位數 k=1 。
對學號的第 k 位執行“計數排序”。完成后，數據會根據第 k 位從小到大排序。
將 k 增加 1 ，然后返回步驟 2. 繼續迭代，直到所有位都排序完成后結束。

/* 獲取元素 num 的第 k 位，其中 exp = 10^(k-1) */
int digit(int num, int exp) {// 傳入 exp 而非 k 可以避免在此重復執行昂貴的次方計算return (num / exp) % 10;
}/* 計數排序（根據 nums 第 k 位排序） */
void countingSortDigit(vector<int> &nums, int exp) {// 十進制的位范圍為 0~9 ，因此需要長度為 10 的桶數組vector<int> counter(10, 0);int n = nums.size();// 統計 0~9 各數字的出現次數for (int i = 0; i < n; i++) {int d = digit(nums[i], exp); // 獲取 nums[i] 第 k 位，記為 dcounter[d]++;                // 統計數字 d 的出現次數}// 求前綴和，將“出現個數”轉換為“數組索引”for (int i = 1; i < 10; i++) {counter[i] += counter[i - 1];}// 倒序遍歷，根據桶內統計結果，將各元素填入 resvector<int> res(n, 0);for (int i = n - 1; i >= 0; i--) {int d = digit(nums[i], exp);int j = counter[d] - 1; // 獲取 d 在數組中的索引 jres[j] = nums[i];       // 將當前元素填入索引 jcounter[d]--;           // 將 d 的數量減 1}// 使用結果覆蓋原數組 numsfor (int i = 0; i < n; i++)nums[i] = res[i];
}/* 基數排序 */
void radixSort(vector<int> &nums) {// 獲取數組的最大元素，用于判斷最大位數int m = *max_element(nums.begin(), nums.end());// 按照從低位到高位的順序遍歷for (int exp = 1; exp <= m; exp *= 10)// 對數組元素的第 k 位執行計數排序// k = 1 -> exp = 1// k = 2 -> exp = 10// 即 exp = 10^(k-1)countingSortDigit(nums, exp);
}

相較于計數排序，基數排序適用于數值范圍較大的情況，但前提是數據必須可以表示為固定位數的格式，且位數不能過大。例如，浮點數不適合使用基數排序，因為其位數 k 過大，可能導致時間復雜度 O(nk)?O(n2) 。

時間復雜度為 O(nk)、非自適應排序：設數據量為 n、數據為 d 進制、最大位數為 k ，則對某一位執行計數排序使用 O(n+d) 時間，排序所有 k 位使用 O((n+d)k) 時間。通常情況下，d 和 k 都相對較小，時間復雜度趨向 O(n) 。
空間復雜度為 O(n+d)、非原地排序：與計數排序相同，基數排序需要借助長度為 n 和 d 的數組 res 和 counter 。
穩定排序：當計數排序穩定時，基數排序也穩定；當計數排序不穩定時，基數排序無法保證得到正確的排序結果。

結論

import time  
import random  
import matplotlib  
matplotlib.use('TkAgg')    # 或 'TkAgg'import matplotlib.pyplot as plt  # 10 common sorting algorithms  
def insertion_sort(arr):  a = arr.copy()  for i in range(1, len(a)):  key = a[i]  j = i - 1  while j >= 0 and a[j] > key:  a[j + 1] = a[j]  j -= 1  a[j + 1] = key  return a  def selection_sort(arr):  a = arr.copy()  for i in range(len(a)):  min_idx = i  for j in range(i+1, len(a)):  if a[j] < a[min_idx]:  min_idx = j  a[i], a[min_idx] = a[min_idx], a[i]  return a  def bubble_sort(arr):  a = arr.copy()  for i in range(len(a)):  for j in range(len(a) - i - 1):  if a[j] > a[j + 1]:  a[j], a[j + 1] = a[j + 1], a[j]  return a  def merge_sort(arr):  if len(arr) <= 1:  return arr  mid = len(arr) // 2  left = merge_sort(arr[:mid])  right = merge_sort(arr[mid:])  return merge(left, right)  def merge(left, right):  result = []  i = j = 0  while i < len(left) and j < len(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 quick_sort(arr):  if len(arr) <= 1:  return arr  pivot = arr[0]  less = [x for x in arr[1:] if x <= pivot]  greater = [x for x in arr[1:] if x > pivot]  return quick_sort(less) + [pivot] + quick_sort(greater)  def heap_sort(arr):  import heapq  a = arr.copy()  heapq.heapify(a)  return [heapq.heappop(a) for _ in range(len(a))]  def counting_sort(arr):  if not arr:  return arr  min_val, max_val = min(arr), max(arr)  count = [0] * (max_val - min_val + 1)  for num in arr:  count[num - min_val] += 1  res = []  for i, c in enumerate(count):  res.extend([i + min_val] * c)  return res  def radix_sort(arr):  if not arr:  return arr  def counting_radix(a, exp):  output = [0]*len(a)  count = [0]*10  for num in a:  count[(num//exp) % 10] += 1  for i in range(1,10):  count[i] += count[i-1]  for num in reversed(a):  idx = (num//exp) % 10  output[count[idx]-1] = num  count[idx] -= 1  return output  max_val = max(arr)  exp = 1  a = arr.copy()  while max_val // exp > 0:  a = counting_radix(a, exp)  exp *= 10  return a  def bucket_sort(arr):  if not arr:  return arr  min_val, max_val = min(arr), max(arr)  bucket_count = 10  interval = (max_val - min_val) / bucket_count  buckets = [[] for _ in range(bucket_count)]  for num in arr:  idx = int((num - min_val) / interval)  if idx == bucket_count:  idx -= 1  buckets[idx].append(num)  res = []  for b in buckets:  res.extend(sorted(b))  return res  def builtin_sort(arr):  return sorted(arr)  # test parameters  
sizes = [100, 500, 1000, 2000, 5000, 10000]  
algos = [insertion_sort, selection_sort, bubble_sort, merge_sort,  quick_sort, heap_sort, counting_sort, radix_sort,  bucket_sort, builtin_sort]  
names = ['Insertion', 'Selection', 'Bubble', 'Merge',  'Quick', 'Heap', 'Counting', 'Radix',  'Bucket', 'Built-in']  
times = {n: [] for n in names}  for n in sizes:  arr = [random.randint(0, n) for _ in range(n)]  for fn, nm in zip(algos, names):  t0 = time.perf_counter()  fn(arr)  t1 = time.perf_counter()  times[nm].append((t1 - t0)*1000)  # plot  
plt.figure(figsize=(8,5))  
for nm in names:  plt.plot(sizes, times[nm], marker='o', label=nm)  
plt.xscale('log'); plt.yscale('log')  
plt.xlabel('Array size n')  
plt.ylabel('Time (ms)')  
plt.title('Sorting Algorithms Performance')  
plt.legend()  
plt.grid(True, which='both', ls='--')  # save to file to avoid backend issue  
plt.savefig('sorting_performance.png', dpi=300)  
print("Plot saved as sorting_performance.png")  # optionally display  
plt.show()

決定排序算法穩定性的關鍵因素

相等元素的比較和交換邏輯
- 穩定排序：當兩個元素相等時，算法不會交換它們或改變它們的相對位置
- 不穩定排序：當兩個元素相等時，算法可能會改變它們的相對位置
排序過程中元素移動/交換的方式
- 如果算法中的元素移動方式會導致相等元素的相對順序發生變化，則該算法是不穩定的
- 特別是當算法進行跨距離的元素交換或移動時，更容易導致不穩定性
算法實現細節
- 有些算法（如快速排序）在標準實現中是不穩定的，但可以通過特定的修改變為穩定排序
- 這些修改通常會增加額外的時間或空間復雜度

穩定性分析

穩定的排序算法

1. 冒泡排序 (Bubble Sort)

穩定原因：只有當前一個元素嚴格大于后一個元素時才交換
代碼中的體現：if (arr[j] > arr[j+1]) swap(arr[j], arr[j+1]);
關鍵判斷：使用 > 而非 >=，確保相等元素不會被交換

for (int i = 0; i < n-1; i++) {for (int j = 0; j < n-i-1; j++) {// 只有當前元素大于后一個元素時才交換，保證穩定性if (arr[j] > arr[j+1]) { swap(arr[j], arr[j+1]);}}
}

2. 插入排序 (Insertion Sort)

穩定原因：在找插入位置時，相等元素不會繼續向前查找
代碼中的體現：while (j >= 0 && arr[j] > key) { arr[j+1] = arr[j]; j--; }
關鍵判斷：使用 > 而非 >=，確保相等元素的相對順序保持不變

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;
}

3. 歸并排序 (Merge Sort)

穩定原因：合并兩個已排序序列時，相等元素的選取有固定的順序
代碼中的體現：if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; }
關鍵判斷：使用 <= 而非 < 處理左側數組元素，確保在相等時選擇左側元素

// 合并兩個有序子數組的函數
void merge(int arr[], int left, int mid, int right) {// ... 初始化臨時數組和指針 ...while (i <= mid && j <= right) {// 關鍵：使用 <= 確保在元素相等時優先選擇左側數組的元素// 這保證了相同元素的相對順序不變if (arr[i] <= arr[j]) {temp[k++] = arr[i++];} else {temp[k++] = arr[j++];}}// ... 處理剩余元素 ...
}

4. 計數排序 (Counting Sort)

穩定原因：處理相同值的元素時按照它們在原始數組中出現的順序
關鍵實現：從右向左掃描原數組并放入結果數組，或使用累加頻率數組

void countingSort(int arr[], int n) {// ... 初始化計數數組和結果數組 ...// 計算每個元素的頻率for (int i = 0; i < n; i++) {count[arr[i]]++;}// 計算累加頻率for (int i = 1; i <= max; i++) {count[i] += count[i-1];}// 關鍵：從右向左遍歷原數組，保證穩定性// 對于相同的元素，先出現的將被放置在較高位置for (int i = n-1; i >= 0; i--) {output[count[arr[i]]-1] = arr[i];count[arr[i]]--;}
}

不穩定的排序算法

1. 選擇排序 (Selection Sort)

不穩定原因：可能會進行相隔較遠的元素交換
關鍵問題代碼：對找到的最小元素進行交換而非移動

for (int i = 0; i < n-1; i++) {int min_idx = i;for (int j = i+1; j < n; j++) {if (arr[j] < arr[min_idx]) {min_idx = j;}}// 問題點：這里的交換可能會改變相等元素的相對順序// 例如[4,2,3,2,1]中，第一次交換后兩個2的相對位置就變了swap(arr[i], arr[min_idx]);
}

2. 快速排序 (Quick Sort)

不穩定原因：分區過程中的交換可能改變相等元素的相對順序
關鍵問題代碼：分區函數中的元素交換

int partition(int arr[], int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] <= pivot) {i++;// 問題點：這里的交換可能會改變與pivot相等元素的相對順序swap(arr[i], arr[j]);}}swap(arr[i+1], arr[high]);return i+1;
}

3. 堆排序 (Heap Sort)

不穩定原因：堆調整過程中的元素交換不考慮元素相等情況
關鍵問題代碼：下沉操作中的交換

void heapify(int arr[], int n, int i) {int largest = i;int left = 2*i + 1;int right = 2*i + 2;if (left < n && arr[left] > arr[largest])largest = left;if (right < n && arr[right] > arr[largest])largest = right;if (largest != i) {// 問題點：這里的交換不考慮相等元素的原始順序// 如果有多個子節點與父節點相等，選擇哪個交換將影響穩定性swap(arr[i], arr[largest]);heapify(arr, n, largest);}
}

4. 希爾排序 (Shell Sort)

不穩定原因：跳躍式的比較和交換會打亂相等元素的相對順序
關鍵問題代碼：跨距離的插入排序

void shellSort(int arr[], int n) {for (int gap = n/2; gap > 0; gap /= 2) {for (int i = gap; i < n; i++) {int temp = arr[i];int j;// 問題點：由于gap大于1，相等元素可能會被錯過或交換順序for (j = i; j >= gap && arr[j-gap] > temp; j -= gap) {arr[j] = arr[j-gap];}arr[j] = temp;}}
}

使不穩定排序變為穩定排序的方法

附加索引信息

// 為元素添加原始位置信息
struct Element {int value;int originalIndex;// 比較運算符重載bool operator<(const Element& other) const {if (value == other.value)return originalIndex < other.originalIndex; // 保持原始順序return value < other.value;}
};void stableSort(int arr[], int n) {// 創建帶索引的元素數組Element* elements = new Element[n];for (int i = 0; i < n; i++) {elements[i].value = arr[i];elements[i].originalIndex = i;}// 使用任意排序算法// 由于比較運算符的重載，相等元素將保持原始順序sort(elements, elements + n);// 將排序結果復制回原數組for (int i = 0; i < n; i++) {arr[i] = elements[i].value;}delete[] elements;
}

修改比較邏輯

// 三路快排示例 - 處理相等元素以保持穩定性
void threeWayQuickSort(int arr[], int low, int high) {if (low >= high) return;int lt = low, gt = high;int pivot = arr[low];int i = low + 1;while (i <= gt) {if (arr[i] < pivot) {swap(arr[lt++], arr[i++]);} else if (arr[i] > pivot) {swap(arr[i], arr[gt--]);} else {// 相等元素不交換，保持原有順序i++;}}threeWayQuickSort(arr, low, lt - 1);threeWayQuickSort(arr, gt + 1, high);
}

穩定性的實際應用

穩定排序在以下情況特別重要：

多級排序

// 使用穩定排序實現多級排序
// 例如：按照分數排序，分數相同的按照學號排序
void multiLevelSort(Student students[], int n) {// 首先，按照學號排序（次要關鍵字）// 使用穩定的排序算法如歸并排序mergeSort(students, 0, n-1, compareByStudentId);// 然后，按照分數排序（主要關鍵字）// 由于使用了穩定排序，分數相同的學生將保持按學號排序的順序mergeSort(students, 0, n-1, compareByScore);
}

保留用戶自定義順序 在用戶界面應用中，當多個元素具有相同優先級時，保持它們的原始排列順序可以提供更一致的用戶體驗。
數據可視化和報表生成 當相等數據的顯示順序對用戶體驗有影響時，穩定排序可以確保一致的呈現方式，增強用戶對數據的理解和分析。

現實排序庫的實現（o4mini）

在工業級、通用排序庫里，最常見的組合是“歸并（或歸并變種）＋小規模時用插入”，主要原因有以下幾點：

1. 插入排序（Insertion Sort）在小規模或近乎有序時最快

低常數開銷：插入排序的邏輯非常簡單，幾乎只做一趟向前比較／搬移。對于 n≤16 甚至更小的規模，其函數調用、遞歸或復雜分支帶來的開銷往往高于算法本身的比較和交換成本。
適應性強：對于已經“部分有序”的數據（例如幾乎排好序的數組、或者只有少量亂序），插入排序能接近線性表現 O(n+f)，而普通的 O(n log n) 算法就難以利用這點優勢。
簡單易實現、易優化：很容易寫出分支預測友好、基于移動（memmove）的高性能版本。

因此主流的各種分治式排序（快速、歸并、希爾、堆……）在分到一定閾值時，普遍會切換成插入排序來“收尾”。

2. 歸并排序（Merge Sort）及其變種的優勢

最壞時間復雜度穩定：總是 O(n log n)，不會像快速排序那樣在某些輸入（例如幾乎有序、極端分布）退化到 O(n2)。
穩定性：天然保持相等元素的相對先后次序。對于需要穩定排序（比如數據庫多字段排序）幾乎是唯一選擇。
外部排序友好：歸并可以在磁盤／SSD等外存上分批讀寫，很容易做 k 路歸并；而其他比較排序就不那么自然。
易于并行化、多路歸并：現代 CPU 的向量化、NUMA 內存架構，都能通過分塊歸并更好利用。

所以像 C++ 的 std::stable_sort 底層就是歸并；Java、Python 等語言的內置穩定排序（Java 的 TimSort、Python 的 Timsort）都是在歸并的基礎上，又加入了對已有“遞增／遞減 runs” 的“天然合并”＋“galloping”（快速跳躍）技術。

3. 為什么不廣泛用“其他”算法？

快速排序（Quick Sort）：常數因子小、平均最快，但最差 O(n2)，需額外防護（隨機化、三數取中、切換堆排序）才能保證線性對數級別。
堆排序（Heap Sort）：最壞 O(n log n)、不占額外空間，但常數因子較大，內存訪問不連貫，分支預測差，實際比歸并/快速都慢。
希爾排序（Shell Sort）：對一般類型不穩定，增量序列調優困難，對各種分布的普適性和可預測性不如歸并/快速。
基數排序（Radix Sort）：雖然能到 O(n) 級別，但對類型（整數、浮點）、鍵長度／位寬敏感，需要額外內存，不如歸并在接口上通用。

4. 實際庫里常見的“混合套路”

C++ std::sort：典型的 Introsort ——先快速排序，若遞歸層數過深再切堆排序，分到小塊時切插入排序。
C++ std::stable_sort：歸并排序＋分塊優化＋插入排序收尾。
Java Arrays.sort(Object[]) & Python list.sort()：都是 TimSort（歸并＋插入＋“galloping”合并），利用已有有序片段，對典型數據集（部分排序、少量亂序）非常快。
TimSort

小結：