排序算法：歸並排序 Java 實現

歸並排序基於歸並操作，是分治法的典型應用。

基本思想

1. 將數組分成 A、B 兩組。
2. 遞歸分解至單元素（視為有序）。
3. 合併相鄰有序小組。
4. 先分解後合併完成排序。

兩個有序數組合併

private static void mergeArray(int[] A, int lenA, int[] B, int lenB, int[] temp) {
    int i = 0, j = 0, k = 0;
    while (i < lenA && j < lenB) {
        temp[k++] = (A[i] > B[j]) ? B[j++] : A[i++];
    }
    while (i < lenA) temp[k++] = A[i++];
    while (j < lenB) temp[k++] = B[j++];
}

完整遞歸實現

public class MergeSorter {
    public void sort(int[] array) {
        int[] aux = new int[array.length];
        mergeSort(array, aux, 0, array.length - 1);
    }

    private void mergeSort(int[] array, int[] aux, int low, int high) {
        if (low < high) {
            int mid = (low + high) / 2;
            mergeSort(array, aux, low, mid);
            mergeSort(array, aux, mid + 1, high);
            mergeArray(array, aux, low, mid, high);
        }
    }

    private void mergeArray(int[] array, int[] temp, int low, int mid, int high) {
        int i = low, j = mid + 1, k = 0;
        while (i <= mid && j <= high) {
            temp[k++] = (array[i] > array[j]) ? array[j++] : array[i++];
        }
        while (i <= mid) temp[k++] = array[i++];
        while (j <= high) temp[k++] = array[j++];
        for (i = low, k = 0; i <= high; i++, k++) array[i] = temp[k];
    }
}

參考資料

1. 歸並排序詳解
2. 更多實現