归并排序（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 < right)
    {
        int mid = left + ((right - 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)，并且适用于各种数据类型的排序，因此在实际应用中仍然有广泛的应用。