歸并排序（Merge Sort）是一種分而治之的算法，它將原始數組分成越來越小的子數組，直到每個子數組只有一個元素，然后將這些子數組兩兩合并，過程中保持排序狀態，最終合并成一個完全有序的數組。歸并排序是一種穩定的排序算法，其主要特點是效率高且易于理解。

歸并排序的基本步驟：

1. 分解：將當前區間一分為二，即求中點。
2. 遞歸排序：遞歸地對兩個子區間a[low...mid]和a[mid+1...high]進行歸并排序。
3. 合并：將已排序的兩個子區間合并成一個有序區間。

時間復雜度和空間復雜度：

• 時間復雜度：歸并排序的時間復雜度為O(n log n)，無論是最好、最壞還是平均情況都是如此，因為它總是將數組分成兩半進行處理，然后合并，這個過程與數組的初始狀態無關。

• 空間復雜度：由于歸并排序需要一個與原數組相同大小的臨時數組來合并子數組，所以其空間復雜度為O(n)。

穩定性**：

歸并排序是穩定的排序算法，因為在合并兩個子數組時，如果遇到相等的元素，會先將左側子數組的元素加入結果數組，保持原有順序不變。

以下是歸并排序的實現示例圖：

以下是實現歸并排序的Java代碼：

public class MergeSort {// 合并兩個子數組private static void merge(int[] arr, int left, int mid, int right, int[] temp) {int i = left, j = mid + 1, k = 0;while (i <= mid && j <= right) {if (arr[i] <= arr[j]) {temp[k++] = arr[i++];} else {temp[k++] = arr[j++];}}while (i <= mid) {temp[k++] = arr[i++];}while (j <= right) {temp[k++] = arr[j++];}// 將排序后的元素復制回原數組System.arraycopy(temp, 0, arr, left, right - left + 1);}// 主函數，遞歸進行歸并排序public static void mergeSort(int[] arr, int left, int right, int[] temp) {if (left < right) {int mid = (left + right) / 2;mergeSort(arr, left, mid, temp); // 排序左半部分mergeSort(arr, mid + 1, right, temp); // 排序右半部分merge(arr, left, mid, right, temp); // 合并兩個有序部分}}public static void main(String[] args) {int[] arr = {12, 11, 13, 5, 6, 7};int[] temp = new int[arr.length];mergeSort(arr, 0, arr.length - 1, temp);System.out.println("Sorted array: ");for (int num : arr) {System.out.print(num + " ");}}
}