歸併排序（Merge Sort）

一、基本介紹

歸併排序是一種分治思想的經典排序演算法，它將原序列分成若干個子序列，通過遞歸再將序列合併起來。根據分治的思想，歸併排序的時間複雜度始終穩定在 O(nlogn)。

二、演算法描述

歸併排序演算法可以描述為分為兩步：分離和歸併。

1. 分離

為了使歸併排序可以遞歸地運行，需要將原序列分割成若干子序列，使得每個子序列的長度均為1，即子序列不可再分。然後將子序列兩兩合併，合併後的序列長度為2，繼續兩兩合併，以此類推，直到合併成原序列。

void merge_sort(int arr[], int left, int right)
{
    if (left >= right) return;

    int mid = left + (right - left) / 2;

    merge_sort(arr, left, mid);
    merge_sort(arr, mid + 1, right);

    merge(arr, left, mid, right);
}

2. 歸併

歸併是指將已經排好序的兩個子序列合併成一個序列的過程。在合併的過程中，需要使用一個臨時數組來保持排序的結果，最終將臨時數組內容複製回原數組。

void merge(int arr[], int left, int mid, int right) 
{
    int temp[right - left + 1];
    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++];

    for (i = left, k = 0; i <= right; ++i, ++k)
        arr[i] = temp[k];
}

三、優化方法

歸併排序演算法的關鍵在於歸併過程，因此如何優化歸併過程對演算法的性能影響較大。以下是幾種常見的優化方法：

1. 優化歸併過程

對於一些小規模數組，直接使用插入排序。經過實驗，如果數組長度為16以下時，插入排序的效率更高。

void merge_sort(int arr[], int left, int right)
{
    if (left + 16 >= right)
    {
        insert_sort(arr + left, right - left + 1);
        return;
    }

    int mid = left + (right - left) / 2;

    merge_sort(arr, left, mid);
    merge_sort(arr, mid + 1, right);

    merge(arr, left, mid, right);
}

2. 避免重複申請空間

歸併過程需要一個臨時數組來保存排序好的元素，但是每次遞歸都會申請一個新的數組，這樣會浪費空間。因此，在函數開始時申請一次空間即可，然後在遞歸的過程中直接使用同一個數組。

void merge_sort(int arr[], int left, int right, int temp[])
{
    if (left >= right) return;

    int mid = left + (right - left) / 2;

    merge_sort(arr, left, mid, temp);
    merge_sort(arr, mid + 1, right, temp);

    merge(arr, left, mid, right, temp);
}

void merge(int arr[], int left, int mid, int right, int temp[]) 
{
    // 省略
}

3. 使用尾遞歸優化

尾遞歸優化可以避免遞歸調用帶來的棧空間開銷。在歸併排序中，遞歸調用發生在分離兩個子序列的過程中。這裡採用尾遞歸優化方法，將遞歸過程轉換為循環過程，可以避免遞歸調用的棧空間開銷。

void merge_sort(int arr[], int left, int right, int temp[])
{
    while (left > 1);

        merge_sort(arr, left, mid, temp);
        left = mid + 1;
    }
}

void merge(int arr[], int left, int mid, int right, int temp[]) 
{
    // 省略
}

四、總結

歸併排序雖然有些優化方法，但它的時間複雜度始終穩定在 O(nlogn)，並且適用於各種數據類型的排序，因此在實際應用中仍然有廣泛的應用。