> For the complete documentation index, see [llms.txt](https://jun-wang.gitbook.io/learnjava/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jun-wang.gitbook.io/learnjava/ji-shu-xue-xi/suan-fa/pai-xu-suan-fa/gui-bing-pai-xu.md).

# 归并排序

## 1. 简介

归并排序的算法是将多个有序数据表合并成一个有序数据表。如果参与合并的只有两个有序表，则称为二路合并。对于一个原始的待排序数列，往往可以通过分割的方法来归结为多路合并排序。

## 2. 归并排序思路

1. 将长度为n的待排序数组看做是由n个有序长度为1的数组组成
2. 将其两两合并，得到长度为2的有序数组
3. 然后再对这些子表进行合并，得到长度为4的有序数组
4. 重复上述过程，一直到最后的子表长度为n也就完成了排序

## 3. 代码实例

归并排序有两种实现方式：递归和非递归。在看归并排序的代码之前先来看一下怎么和合并两个有序数组：

```java
// 基础，合并两个有序数组
public static int[] merge2Arr(int[] arr1, int[] arr2) {
  int len1 = arr1.length;
  int len2 = arr2.length;
  int[] res = new int[len1 + len2];  // 使用一个数组用来存储排好序的数组
  int i = 0, j = 0, k = 0;
  while(i < len1 && j < len2) {
    res[k++] = arr1[i] < arr2[j]? arr1[i++] : arr2[j++];
  }
  while(i < len1) {
    res[k++] = arr1[i++];
  }
  while(j < len2) {
    res[k++] = arr2[j++];
  }
  return res;
}
```

### 归并排序的递归实现：

```java
// 归并排序，递归实现
public void sortMergeRecursion(int[] nums) {
  sortMergeRecursionHelper(nums, 0, nums.length - 1);
}
public void sortMergeRecursionHelper(int[] nums,int left, int right) {
  if(left == right) return;  // 当待排序的序列长度为1时，递归开始回溯，进行merge
  int middle = left + (right - left) / 2;
  sortMergeRecursionHelper(nums, left, middle); //左半部分排好序
  sortMergeRecursionHelper(nums, middle + 1, right);  //有半部分排好序
  mergeArr(nums, left, middle, right);
}
public void mergeArr(int[] nums, int left, int middle, int right) {
  int[] tem = new int[right - left + 1];
  int i = left, j = middle + 1, k = 0;
  while(i <= middle && j <= right) {
    tem[k++] = nums[i] < nums[j]? nums[i++] : nums[j++];
  }
  while(i <= middle) {
    tem[k++] = nums[i++];
  }
  while(j <= right) {
    tem[k++] = nums[j++];
  }
  // 将辅助数组数据写入原数组
  int index = 0;
  while(left <= right) {
    nums[left++] = tem[index++];
  }
}
```

### 归并排序的非递归实现（迭代）：

```java
// 归并排序，非递归实现(迭代)
public void sortMergeIteration(int[] nums) {
  int len = 1;  // 初始排序数组的长度
  while(len < nums.length) {
    for(int i = 0; i < nums.length; i += len * 2) {
      sortMergeIterationHelper(nums, i, len);
    }
    len *= 2;  // 每次将排序数组的长度*2
  }
}
/**
 * 辅助函数
 * @param nums  原数组
 * @param start 从start位置开始
 * @param len  本次合并的数组长度
 */
public void sortMergeIterationHelper(int[] nums, int start, int len) {
  int[] tem = new int[len * 2];
  int i = start;
  int j = start + len;
  int k = 0;
  while(i < start + len && (j < start + len + len && j < nums.length)) {
    tem[k++] = nums[i] < nums[j]? nums[i++] : nums[j++];
  }
  while(i < start + len && i < nums.length) {  // 注意：这里i也可能超出长度
    tem[k++] = nums[i++];
  }
  while(j < start + len + len && j < nums.length) {
    tem[k++] = nums[j++];
  }
  int right = start + len + len;
  int index = 0;
  while(start < nums.length && start < right) {
    nums[start++] = tem[index++];
  }
}
```

归并排序的时间复杂度为O(n\*log2n),空间复杂度为O(n)

归并排序是一种稳定的排序方法。

> 参考：
>
> <https://blog.csdn.net/y999666/article/details/50942604>


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jun-wang.gitbook.io/learnjava/ji-shu-xue-xi/suan-fa/pai-xu-suan-fa/gui-bing-pai-xu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.