归并排序精讲：如何优雅实现稳定排序

# 1. 归并排序基础理论

归并排序是一种分而治之的排序算法，将数据分割成更小的单元进行独立排序，然后再将这些有序的单元合并成有序的序列。它属于一种稳定的排序算法，其基本思想可以简单理解为“两个有序序列合并为一个有序序列”。

## 归并排序的工作原理

归并排序主要包含两个操作：分割（Divide）和合并（Conquer）。首先将原始数组分割成较小的数组，直至每个小数组只有一个位置，此时认为小数组已排序完成。接着将小数组两两合并成更大的有序数组，直到最后只有一个排序完成的大数组。

## 归并排序的特点

该算法最显著的特点是其稳定性和非适应性。稳定性意味着排序过程不会改变相同元素间的相对顺序。非适应性表示归并排序不是自适应的，即算法的性能不依赖于输入数据的具体情况。然而，它需要与数组大小成线性的额外空间，这是其缺点之一。

# 2. 归并排序算法详解

## 2.1 归并排序的递归思想

### 2.1.1 分而治之策略

归并排序算法的核心思想是“分而治之”，这是一种递归处理问题的基本策略。具体来说，就是将问题分成若干个小问题，递归求解各个小问题，最后将小问题的解合并成大问题的解。

分而治之策略通常包括三个步骤：

1. 分割：将原始问题分割成子问题，直到子问题足够简单，可以直接求解。
2. 解决：递归地解决问题，如果子问题足够小，则直接求解。
3. 合并：将子问题的解合并成原始问题的解。

在归并排序中，“分割”步骤是将数组分为两个子数组，直到每个子数组只有一个元素；“解决”步骤是递归排序两个子数组；“合并”步骤是将两个已排序的数组合并成一个有序数组。

### 2.1.2 递归实现框架

以下是归并排序的递归实现的基本框架，采用伪代码描述：

function mergeSort(arr)
    if length(arr) <= 1
        return arr
    mid = length(arr) / 2
    left = arr[0...mid-1]
    right = arr[mid...length(arr)-1]
    leftSorted = mergeSort(left)
    rightSorted = mergeSort(right)
    return merge(leftSorted, rightSorted)
end function

这个框架很简洁，它明确了归并排序的递归策略：首先检查数组长度，如果小于或等于1，则不需要排序，直接返回；否则，将数组一分为二，递归排序左右两部分，最后合并这两个已排序的数组。

### 2.2 归并操作的实现

#### 2.2.1 合并过程的伪代码

接下来，详细探讨一下归并操作的实现。合并操作是归并排序中至关重要的步骤，它将两个有序的子数组合并成一个有序数组。以下是合并过程的伪代码：

function merge(left, right)
    result = []
    while length(left) > 0 and length(right) > 0
        if left[0] <= right[0]
            append left[0] to result
            left = left[1...length(left)-1]
        else
            append right[0] to result
            right = right[1...length(right)-1]
    end while
    // 当一个子数组为空时，直接将另一个子数组的剩余部分追加到结果数组中
    while length(left) > 0
        append left[0] to result
        left = left[1...length(left)-1]
    end while
    while length(right) > 0
        append right[0] to result
        right = right[1...length(right)-1]
    end while
    return result
end function

在这个过程中，我们使用两个指针分别指向左右两个数组的起始位置，然后比较两个指针指向的元素，将较小的那个元素添加到结果数组中，并移动该指针。这个过程一直持续到其中一个数组的所有元素都被移动到结果数组中。最后，如果还有一个数组未被完全处理，我们直接将其剩余部分追加到结果数组中。

#### 2.2.2 时间复杂度分析

归并操作是关键操作，其时间复杂度直接影响整个排序算法的效率。归并操作需要比较数组中所有的元素，因此对于含有n个元素的数组，归并操作的时间复杂度为O(n)。由于归并排序需要对数组进行多次分割和合并，其总体时间复杂度为O(n log n)，其中log n是分割数组的层数。

### 2.3 稳定性分析

#### 2.3.1 排序稳定性概念

排序算法的稳定性是指在排序过程中，相等的元素是否保持原有的顺序。一个排序算法是稳定的，当且仅当对于数组中的任意两个相等的元素x和y，如果x在y之前，那么在排序后的数组中，x仍然在y之前。

#### 2.3.2 归并排序的稳定性证明

归并排序是一种稳定的排序算法。在归并操作中，当我们比较两个元素时，只有当左侧数组的元素小于右侧数组的元素时，才会将左侧数组的元素移动到结果数组中。这意味着在合并过程中，任何两个相等的元素的相对位置不会改变，从而保证了排序的稳定性。

为了证明归并排序的稳定性，我们可以观察到合并过程中的每个元素都是从左到右依次比较并添加到结果数组的。如果两个相等的元素都来自左侧数组或右侧数组，它们将被按顺序添加到结果数组中。如果来自不同的数组，则左侧数组的元素会被先添加，这保证了稳定性。

总结来说，归并排序之所以是稳定的排序算法，是因为它通过递归分治的方式，在合并过程中严格保持了元素的相对顺序。这一点在处理大量具有重复键值的记录时尤为重要，因为它能够保证排序结果的一致性和可预测性。

# 3. 归并排序的代码实现

在深入探讨归并排序的代码实现之前，我们需要先理解归并排序算法的核心原理和步骤。归并排序是一种分而治之的排序算法，它将大问题分解为小问题来解决，然后再将小问题的解合并起来，以形成原问题的解。本章节将详细介绍归并排序在不同编程范式中的实现方式，包括面向过程的实现和面向对象的实现，并探讨实际应用中的优化策略。

## 3.1 面向过程的实现

面向过程的实现通常用于性能要求较高的场景，因为它直接且简洁，能够有效利用硬件资源。下面我们将分别用C语言和Java语言实现归并排序。

### 3.1.1 C语言实现

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

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    // 创建临时数组
    int L[n1], R[n2];

    // 拷贝数据到临时数组 L[] 和 R[]
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    // 合并临时数组回 arr[l..r]
    i = 0; // 初始化第一个子数组的索引
    j = 0; // 初始化第二个子数组的索引
    k = l; // 初始合并子数组的索引
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 拷贝 L[] 的剩余元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // 拷贝 R[] 的剩余元素
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        // 找到中间索引
        int m = l + (r - l) / 2;

        // 分别递归排序两半
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        // 合并两半
        merge(arr, l, m, r);
    }
}

// 测试代码
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    printf("Given array is \n");
    for (int i = 0; i < arr_size; i++)
        printf("%d ", arr[i]);
    printf("\n");

    mergeSort(arr, 0, arr_size - 1);

    printf("\nSorted array is \n");
    for (int i = 0; i < arr_size; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

以上是归并排序在C语言中的实现。该实现遵循递归思想，通过`mergeSort`函数对数组进行分割，最终调用`merge`函数合并已排序的子数组。在代码执行过程中，我们需要注意几个关键点：

- `l`和`r`分别代表当前待排序数组的起始和结束索引。
- `m`为中间索引，用于将数组分为两部分。
- 在`merge`函数中，通过比较两个临时数组`L`和`R`中的元素，将较小的元素添加到`arr`数组中，保证了排序的稳定性。

### 3.1.2 Java语言实现

public class MergeSort {

    // 合并两个子数组的函数
    void merge(int arr[], int l, int m, int r) {
        int i, j, k;
        int n1 = m - l + 1;
        int n2 = r - m;

        // 创建临时数组
        int L[] = new int[n1];
        int R[] = new int[n2];

        // 拷贝数据到临时数组 L[] 和 R[]
        for (i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];

        // 合并临时数组回 arr[l..r]
        i = 0; // 初始化第一个子数组的索引
        j = 0; // 初始化第二个子数组的索