C# 兩路歸併排序完整實作與逆序對計數

演算法核心

分治策略：遞歸拆分至單元素，再合併兩有序子陣列。合併過程中計算逆序對數量 (右側元素先於左側元素複製時計數)。

完整代碼

/// 
兩路歸併排序
public static void TwoWayMergeSort(int[] dest, int[] tempDest, int left, int right, ref int swapTimes)
{
    if (left < right)
    {
        int mid = (left + right) / 2;
        TwoWayMergeSort(dest, tempDest, left, mid, ref swapTimes);
        TwoWayMergeSort(dest, tempDest, mid + 1, right, ref swapTimes);
        Merge(dest, tempDest, left, right, mid, ref swapTimes);
    }
}

/// 
合併兩有序區間
private static void Merge(int[] dest, int[] tempDest, int left, int right, int mid, ref int swapTimes)
{
    // 複製到暫存陣列
    for (int i = left; i <= right; i++) tempDest[i] = dest[i];

    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right)
    {
        if (tempDest[i] <= tempDest[j])
            dest[k++] = tempDest[i++];
        else
        {
            dest[k++] = tempDest[j++];
            swapTimes++; // 逆序對計數
        }
    }
    while (j <= right) dest[k++] = tempDest[j++];
    while (i <= mid) dest[k++] = tempDest[i++];
}

關鍵點

• tempDest 需預先分配與 dest 等長。
• swapTimes 以 ref 傳遞累加逆序對總數。
• 穩定排序：<= 保證相等元素相對順序不變。
• 時間複雜度 O(n log n)，空間 O(n)。

可作為 QuickSort 分治對比教學範例，體會遞歸分解與合併的精妙。