歸併排序採用**分治法**:遞歸將數組拆分為單元素,再合併兩個有序數組。時間複雜度穩定 O(n log n),空間複雜度 O(n)。

import java.util.Arrays;
public class MergeSortTest {
public static void main(String[] args) {
int[] arr = {10, 9, 12, 4, 11, 7, 8, 3};
System.out.println("原始: " + Arrays.toString(arr));
sort(arr);
System.out.println("最終: " + Arrays.toString(arr));
}
public static void sort(int[] arr) {
if (arr == null || arr.length < 2) return;
int[] tmp = new int[arr.length]; // 輔助數組,避免重複分配
mergeSort(arr, tmp, 0, arr.length - 1);
}
// 遞歸分治入口
private static void mergeSort(int[] arr, int[] tmp, int left, int right) {
if (left < right) {
int mid = (left + right) >>> 1; // 無符號右移防溢出
mergeSort(arr, tmp, left, mid); // 左半遞歸
mergeSort(arr, tmp, mid + 1, right); // 右半遞歸
merge(arr, tmp, left, mid, right); // 合併
System.out.println("合併後 [" + left + "-" + right + "]: " + Arrays.toString(arr));
}
}
// 合併兩個有序區間 [left, mid] 和 [mid+1, right]
private static void merge(int[] arr, int[] tmp, int left, int mid, int right) {
int i = left; // 左區間指針
int j = mid + 1; // 右區間指針
int k = left; // tmp 寫入指針
// 雙指針歸併
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
else tmp[k++] = arr[j++];
}
// 複製剩餘元素
while (i <= mid) tmp[k++] = arr[i++];
while (j <= right) tmp[k++] = arr[j++];
// 寫回原數組
System.arraycopy(tmp, left, arr, left, right - left + 1);
}
}
原始: [10, 9, 12, 4, 11, 7, 8, 3]
合併後 [0-1]: [9, 10, 12, 4, 11, 7, 8, 3]
合併後 [2-3]: [9, 10, 4, 12, 11, 7, 8, 3]
合併後 [0-3]: [4, 9, 10, 12, 11, 7, 8, 3]
合併後 [4-5]: [4, 9, 10, 12, 7, 11, 8, 3]
合併後 [6-7]: [4, 9, 10, 12, 7, 11, 3, 8]
合併後 [4-7]: [4, 9, 10, 12, 3, 7, 8, 11]
合併後 [0-7]: [3, 4, 7, 8, 9, 10, 11, 12]
最終: [3, 4, 7, 8, 9, 10, 11, 12]
tmp 在頂層分配一次,遞歸傳遞複用,避免 O(n log n) 空間浪費。System.arraycopy 批量拷貝 比手寫循環快 (JVM 內部優化)。arr[i] <= arr[j] 保證相等元素相對順序不變。| 算法 | 平均時間 | 最差時間 | 空間 | 穩定 |
|---|---|---|---|---|
| 歸併排序 | O(n log n) | O(n log n) | O(n) | ✅ |
| 快速排序 | O(n log n) | O(n²) | O(log n) | ❌ |
| 堆排序 | O(n log n) | O(n log n) | O(1) | ❌ |
| TimSort (Java/JDK) | O(n log n) | O(n log n) | O(n) | ✅ |
Java Arrays.sort() 對象數組用 TimSort (歸併+插入優化),基本類型用雙軸快排。理解歸併排序是掌握分治思想、外部排序、倒序數統計的基石。