参考：https://www.cnblogs.com/chengxiao/p/6194356.html

定义

归并排序 是一种采用分治法（Divide and Conquer）的排序算法。它将一个大问题分解为若干个小问题，递归地解决这些小问题，然后将结果合并得到最终解。归并排序通过将数组不断分割成更小的子数组，直到每个子数组只有一个元素，然后将这些子数组逐步合并并排序。

实现步骤

1. 分解（Divide）：将待排序数组从中间分成两个子数组
2. 解决（Conquer）：递归地对两个子数组进行归并排序
3. 合并（Combine）：将两个已排序的子数组合并成一个有序数组

分而治之

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。

C语言实现

#include <stdio.h>
#include <stdlib.h>

/* 合并两个已排序的子数组 */
void merge(int arr[], int leftStart, int middle, int rightEnd)
{
    int leftIndex, rightIndex, mergedIndex;
    int leftSize = middle - leftStart + 1; /* 左子数组大小 */
    int rightSize = rightEnd - middle;     /* 右子数组大小 */

    /* 创建临时数组存储左右子数组 */
    int *leftTempArray = (int *)malloc(leftSize * sizeof(int));
    int *rightTempArray = (int *)malloc(rightSize * sizeof(int));

    /* 复制数据到临时数组 */
    for (leftIndex = 0; leftIndex < leftSize; leftIndex++)
        leftTempArray[leftIndex] = arr[leftStart + leftIndex];
    for (rightIndex = 0; rightIndex < rightSize; rightIndex++)
        rightTempArray[rightIndex] = arr[middle + 1 + rightIndex];

    /* 合并临时数组回到原始数据 */
    leftIndex = 0;           /* 左子数组的当前索引 */
    rightIndex = 0;          /* 右子数组的当前索引 */
    mergedIndex = leftStart; /* 合并后数组的当前索引 */

    /* */
    while (leftIndex < leftSize && rightIndex < rightSize)
    {
        if (leftTempArray[leftIndex] <= rightTempArray[rightIndex])
        {
            arr[mergedIndex] = leftTempArray[leftIndex];
            leftIndex++;
        }
        else
        {
            arr[mergedIndex] = rightTempArray[rightIndex];
            rightIndex++;
        }
        mergedIndex++;
    }

    /* 复制左子数组中剩余的元素 */
    while (leftIndex < leftSize)
    {
        arr[mergedIndex] = leftTempArray[leftIndex];
        leftIndex++;
        mergedIndex++;
    }

    /* 复制右子数组中剩余的元素 */
    while (rightIndex < rightSize)
    {
        arr[mergedIndex] = rightTempArray[rightIndex];
        rightIndex++;
        mergedIndex++;
    }

    /* 释放临时数组内存 */
    free(leftTempArray);
    free(rightTempArray);
}

/* 归并排序主函数 */
void mergeSort(int arr[], int leftBound, int rightBound)
{
    if (leftBound < rightBound)
    {
        /* 找到中点， 避免溢出 */
        int midPoint = leftBound + (rightBound - leftBound) / 2;

        /* 递归排序左右子数组 */
        mergeSort(arr, leftBound, midPoint);
        mergeSort(arr, midPoint + 1, rightBound);

        /* 合并已排序的子数组 */
        merge(arr, leftBound, midPoint, rightBound);
    }
}

/* 打印数组函数 */
void printArray(int arr[], int arraysize)
{
    int elementIndex;
    for (elementIndex = 0; elementIndex < arraysize; elementIndex++)
    {
        printf("%d ", arr[elementIndex]);
    }
    printf("\n");
}

/* 测试归并排序 */
int main(void)
{
    int testArray[] = {8, 4, 5, 7, 1, 3, 6, 2};
    int arraySize = sizeof(testArray) / sizeof(testArray[0]);

    printf("原始数组： \n");
    printArray(testArray, arraySize);

    mergeSort(testArray, 0, arraySize - 1);

    printf("排序后数组： \n");
    printArray(testArray, arraySize);

    return 0;
}

原始数组： 
8 4 5 7 1 3 6 2 
排序后数组： 
1 2 3 4 5 6 7 8 

[Done] exited with code=0 in 0.39 seconds

复杂度分析

2.1 递归深度

对于大小为 n 的数组，每次递归都将数组分成两半：
– 第0层: 1个大小为n的数组
– 第1层: 2个大小为n/2的数组
– 第2层: 4个大小为n/4的数组
– …
– 第k层: 2^k个大小为n/2^k的数组

当数组大小为1时停止分割，即 n/2^k = 1，解得 k = log₂n
所以递归深度为 log₂n + 1，即 O(log n)

2.2 每层的工作量

在每一层，我们需要合并所有子数组，总的元素数量仍然是 n：
– 第0层: 合并2个大小为n/2的数组 → 工作量 O(n)
– 第1层: 合并4个大小为n/4的数组 → 工作量 O(n)
– …
– 每一层的工作量都是 O(n)

3. 总时间复杂度推导

由于有 log n 层，每层工作量为 O(n)，所以总时间复杂度为：
T(n) = O(n) * O(log n) = O(n log n)

4. 数学推导

递归关系式：
T(n) = 2*T(n/2) + O(n)

使用主定理（Master Theorem）求解：
– a = 2, b = 2, f(n) = O(n)
– log_b(a) = log₂(2) = 1
– f(n) = O(n) = O(n^1)
– 因为 f(n) = Θ(n^(log_b(a)))，所以 T(n) = O(n log n)

5. 空间复杂度

归并排序需要额外的存储空间来存储临时数组：
– 在合并过程中，需要创建两个临时数组，大小分别为 n/2
– 递归调用栈的深度为 O(log n)
– 所以总空间复杂度为 O(n) + O(log n) = O(n)