归并排序

基本思想

归并排序（Merge Sort）是一种典型的分治算法：先将数组不断拆成两半，直到每个子数组只剩一个元素，再逐层合并有序的子数组。

重点： 单个元素天然有序；真正完成排序的关键，是将两个已经有序的子数组合并成一个有序数组。

排序过程

以数组 [38, 12, 27, 43, 9, 31, 18, 25] 为例。

1. 拆分

不断将数组一分为二，直到子数组只剩一个元素：

[38, 12, 27, 43, 9, 31, 18, 25]
                  ↓
[38, 12, 27, 43]          [9, 31, 18, 25]
        ↓                        ↓
[38, 12] [27, 43]        [9, 31] [18, 25]
    ↓       ↓               ↓       ↓
[38][12] [27][43]        [9][31] [18][25]

2. 合并

合并时，分别用一个指针指向两个有序子数组的首元素：

1. 比较两个指针指向的元素，将较小者放入临时数组，并移动对应指针。
2. 重复比较，直到一个子数组的元素全部取完。
3. 将另一个子数组剩余的元素依次放入临时数组。
4. 将合并结果复制回原数组对应的区间。

例如，合并 [12, 38] 和 [27, 43]：

整个数组逐层合并的过程如下：

[38] + [12] → [12, 38]
[27] + [43] → [27, 43]
[9]  + [31] → [9, 31]
[18] + [25] → [18, 25]

[12, 38] + [27, 43] → [12, 27, 38, 43]
[9, 31]  + [18, 25] → [9, 18, 25, 31]

[12, 27, 38, 43] + [9, 18, 25, 31]
→ [9, 12, 18, 25, 27, 31, 38, 43]

复杂度与稳定性

每次将数组分成两半，拆分深度为 $O(\log n)$；每一层合并时，总共处理 $n$ 个元素，耗时为 $O(n)$。因此，总时间复杂度为：

稳定性的关键是合并时使用 <=。 相等时先取左侧元素，才能保留它们在原数组中的相对顺序。

C++ 实现

三个函数分别负责：

• Merge：合并相邻的两个有序区间 [leftPos, rightPos - 1] 和 [rightPos, rightEnd]。
• Msort：递归拆分区间 [left, right]，再调用 Merge 合并。
• MergeSort：分配临时数组、启动排序，最后释放空间。

#include <iostream>
#include <new>

using ElementType = int;

void Merge(ElementType A[], ElementType tmpArray[],
           int leftPos, int rightPos, int rightEnd) {
    int leftEnd = rightPos - 1;
    int elementNum = rightEnd - leftPos + 1;
    int tmpPos = leftPos;

    while (leftPos <= leftEnd && rightPos <= rightEnd) {
        // 相等时优先取左侧元素，保证稳定性。
        if (A[leftPos] <= A[rightPos]) {
            tmpArray[tmpPos++] = A[leftPos++];
        } else {
            tmpArray[tmpPos++] = A[rightPos++];
        }
    }

    while (leftPos <= leftEnd) {
        tmpArray[tmpPos++] = A[leftPos++];
    }

    while (rightPos <= rightEnd) {
        tmpArray[tmpPos++] = A[rightPos++];
    }

    // 将本次合并的区间复制回原数组。
    for (int i = 0; i < elementNum; ++i, rightEnd--) {
        A[rightEnd] = tmpArray[rightEnd];
    }
}

void Msort(ElementType A[], ElementType tmpArray[], int left, int right) {
    if (left < right) {
        int center = left + (right - left) / 2;

        Msort(A, tmpArray, left, center);
        Msort(A, tmpArray, center + 1, right);

        Merge(A, tmpArray, left, center + 1, right);
    }
}

void MergeSort(ElementType A[], int n) {
    ElementType* tmpArray = nullptr;

    try {
        tmpArray = new ElementType[n];
    } catch (const std::bad_alloc&) {
        std::cerr << "No space for tmpArray!" << std::endl;
        return;
    }

    Msort(A, tmpArray, 0, n - 1);

    delete[] tmpArray;
}

调用示例（接在上述代码后）：

int main() {
    ElementType nums[] = {38, 12, 27, 43, 9, 31};
    int n = sizeof(nums) / sizeof(nums[0]);

    MergeSort(nums, n);

    for (int i = 0; i < n; ++i) {
        std::cout << nums[i] << (i + 1 == n ? '\n' : ' ');
    }

    return 0;
}

输出：

9 12 27 31 38 43