# 归并排序（Merge Sort）

URL: https://caijiao.org/sort/5-merge-sort
Source: docs/sort/5-merge-sort.md
Description: 介绍归并排序的分治法思想、稳定性特点和适用场景，附带 JavaScript、Python、C++、Java、PHP、Go 多语言实现及详细解析，帮助深入理解。

归并排序是一种经典的 **分治算法**，通过将大问题递归拆分为小问题分别解决，最后再合并结果完成整体排序。它具备**稳定性高**、**时间复杂度恒定为 O(n log n)** 的特点，适用于对稳定性要求较高的场景。

## 📌 算法原理解释

归并排序采用 **“分而治之”** 的思想：

1. 将数组不断二分（直到只剩一个元素为止）；
2. 从底向上合并两个有序数组；
3. 在合并过程中进行排序。

例如 `[5, 3, 8, 4]` 会先分为 `[5, 3]` 和 `[8, 4]`，再分为 `[5] [3] [8] [4]`，然后合并为 `[3, 5] [4, 8]`，最终合并为 `[3, 4, 5, 8]`。

优点：性能稳定，适合大规模数据。  
缺点：额外的 O(n) 空间复杂度。

## 💻 多语言代码实现


// JavaScript 归并排序
function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    result.push(left[i] <= right[j] ? left[i++] : right[j++]);
  }
  return result.concat(left.slice(i)).concat(right.slice(j));
}
````

```python
# Python 归并排序
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result
```

```cpp
// C++ 归并排序
#include <vector>
using namespace std;

void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> temp;
    int i = left, j = mid + 1;
    while(i <= mid && j <= right) {
        if(arr[i] <= arr[j]) temp.push_back(arr[i++]);
        else temp.push_back(arr[j++]);
    }
    while(i <= mid) temp.push_back(arr[i++]);
    while(j <= right) temp.push_back(arr[j++]);

    for(int k = 0; k < temp.size(); ++k) {
        arr[left + k] = temp[k];
    }
}

void mergeSort(vector<int>& arr, int left, int right) {
    if(left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}
```

```java
// Java 归并排序
public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left >= right) return;
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    private static void merge(int[] arr, int l, int m, int r) {
        int[] temp = new int[r - l + 1];
        int i = l, j = m + 1, k = 0;
        while (i <= m && j <= r) {
            temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
        while (i <= m) temp[k++] = arr[i++];
        while (j <= r) temp[k++] = arr[j++];
        System.arraycopy(temp, 0, arr, l, temp.length);
    }
}
```

```php
<?php
// PHP 归并排序
function mergeSort(array $arr): array {
    if (count($arr) <= 1) return $arr;
    $mid = intdiv(count($arr), 2);
    $left = mergeSort(array_slice($arr, 0, $mid));
    $right = mergeSort(array_slice($arr, $mid));
    return merge($left, $right);
}

function merge(array $left, array $right): array {
    $result = [];
    while (count($left) && count($right)) {
        $result[] = $left[0] <= $right[0] ? array_shift($left) : array_shift($right);
    }
    return array_merge($result, $left, $right);
}
?>
```

```go
// Go 归并排序
package main

func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    mid := len(arr) / 2
    left := mergeSort(arr[:mid])
    right := mergeSort(arr[mid:])
    return merge(left, right)
}

func merge(left, right []int) []int {
    result := make([]int, 0, len(left)+len(right))
    i, j := 0, 0
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }
    result = append(result, left[i:]...)
    result = append(result, right[j:]...)
    return result
}
```


## ✅ 算法特点与总结

| 属性     | 描述           |
| ------ | ------------ |
| 时间复杂度  | O(n log n)   |
| 空间复杂度  | O(n)（需要辅助数组） |
| 稳定性    | ✅ 稳定         |
| 是否原地排序 | ❌ 否（使用额外空间）  |

> 📌 提示：归并排序适合处理**链表**、\*\*外部排序（如大文件排序）\*\*等需要稳定性的应用场景。