Java 遞歸歸並排序演算法完整實現與解析

歸並排序是一種經典的分治法演算法，其核心思想是將兩個已經有序的陣列合併成一個有序陣列。透過遞歸不斷將大陣列拆分為兩半，直到每個子陣列只剩一個元素（單一元素視為有序），再逐層合併，最終得到完全排序的陣列。

演算法運作流程

1. 分割：將陣列從中點切分為左右兩部分

2. 遞歸排序：對左右兩部分分別呼叫歸並排序

3. 合併：將兩個已排序的子陣列合併為一個有序陣列

Java 完整程式碼實現

import java.util.*;

public class MergeSortTest {

    public static void main(String[] args) {
        int arr[] = new int[]{10, 9, 12, 4, 11, 7, 8, 3};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int arr[]) {
        int tmpArray[] = new int[arr.length];
        mergeSort(arr, tmpArray, 0, arr.length - 1);
    }

    private static void mergeSort(int arr[], int tmpArray[], int first, int last) {
        if (first < last) {
            int mid = (first + last) / 2;
            mergeSort(arr, tmpArray, first, mid);
            mergeSort(arr, tmpArray, mid + 1, last);
            merge(arr, tmpArray, first, mid, last);
            System.out.println(Arrays.toString(arr));
        }
    }

    private static void merge(int a[], int tmpArray[], int first, int mid, int last) {
        int beginHalf1 = first;
        int endHalf1 = mid;
        int beginHalf2 = mid + 1;
        int endHalf2 = last;
        int index = beginHalf1;
        int num = last - first + 1;

        while (beginHalf1 <= endHalf1 && beginHalf2 <= endHalf2) {
            if (a[beginHalf1] <= a[beginHalf2]) {
                tmpArray[index++] = a[beginHalf1++];
            } else {
                tmpArray[index++] = a[beginHalf2++];
            }
        }

        while (beginHalf1 <= endHalf1) {
            tmpArray[index++] = a[beginHalf1++];
        }
        while (beginHalf2 <= endHalf2) {
            tmpArray[index++] = a[beginHalf2++];
        }

        for (int i = 0; i < num; i++, endHalf2--) {
            a[endHalf2] = tmpArray[endHalf2];
        }
    }
}

執行結果示例

對陣列 {10, 9, 12, 4, 11, 7, 8, 3} 排序的過程輸出：

[9, 10, 12, 4, 11, 7, 8, 3]
[9, 10, 4, 12, 11, 7, 8, 3]
[4, 9, 10, 12, 11, 7, 8, 3]
[4, 9, 10, 12, 7, 11, 8, 3]
[4, 9, 10, 12, 7, 11, 3, 8]
[4, 9, 10, 12, 3, 7, 8, 11]
[3, 4, 7, 8, 9, 10, 11, 12]
[3, 4, 7, 8, 9, 10, 11, 12]

複雜度分析

• 時間複雜度：O(n log n) - 穩定且效能優異
• 空間複雜度：O(n) - 需要額外暫存陣列
• 穩定性：穩定排序 - 相等元素相對順序不變

歸並排序適用於大量資料排序，且是外部排序的基礎演算法之一。