什么是归并排序？

归并排序（Merge Sort） 是一种基于分治思想的稳定排序算法，由John von Neumann于1945年提出。它将数组递归地分成两半分别排序，然后再合并起来。归并排序的最大特点是稳定性——相等元素的相对顺序在排序后保持不变。

归并排序的核心思想

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

C++ 代码实现

#include <iostream>
#include <vector>
using namespace std;

// 合并两个有序数组
void merge(vector<int>& arr, int left, int mid, int right) {
    // 创建临时数组
    vector<int> temp(right - left + 1);
    
    int i = left;      // 左半部分指针
    int j = mid + 1;   // 右半部分指针
    int 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 (int p = 0; p < k; p++) {
        arr[left + p] = temp[p];
    }
}

// 归并排序主函数
void merge_sort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        // 递归排序左右两部分
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
        
        // 合并
        merge(arr, left, mid, right);
    }
}

// 原地归并排序（节省空间，但效率略低）
void merge_inplace(vector<int>& arr, int left, int mid, int right) {
    int i = left, j = mid + 1;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            i++;
        } else {
            // arr[i] > arr[j]，需要将arr[j]插入到前面
            int temp = arr[j];
            // 将arr[i..j-1]向后移动一位
            for (int k = j; k > i; k--) {
                arr[k] = arr[k - 1];
            }
            arr[i] = temp;
            i++;
            mid++;
            j++;
        }
    }
}

int main() {
    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
    int n = arr.size();
    
    cout << "排序前: ";
    for (int x : arr) cout << x << " ";
    cout << endl;
    
    merge_sort(arr, 0, n - 1);
    
    cout << "排序后: ";
    for (int x : arr) cout << x << " ";
    cout << endl;
    
    return 0;
}

迭代版归并排序

递归版本可能导致栈溢出，迭代版本可以避免这个问题：

void merge_sort_iterative(vector<int>& arr) {
    int n = arr.size();
    
    // 从子数组大小为1开始，逐渐增大
    for (int size = 1; size < n; size *= 2) {
        // 遍历所有需要合并的子数组对
        for (int left = 0; left < n; left += 2 * size) {
            int mid = min(left + size - 1, n - 1);
            int right = min(left + 2 * size - 1, n - 1);
            
            if (mid < right) {
                merge(arr, left, mid, right);
            }
        }
    }
}

复杂度分析

归并排序的应用场景

1. 外部排序：当数据量太大无法全部加载到内存时
2. 链表排序：O(n log n) 稳定排序
3. 逆序对计数：利用归并过程计算逆序对
4. 并行排序：易于并行化处理

总结

归并排序是一种经典的分治算法，其稳定性使其在需要保持元素相对顺序的场景中不可替代。虽然需要 O(n) 的额外空间，但其稳定性和保证的 O(n log n) 时间复杂度使其成为重要的排序算法。理解归并排序对于学习更复杂的算法（如归并树、CDQ分治等）也很有帮助。