一、算法思想

归并排序是最流行的排序算法之一，它基于分而治之算法的原理。在这里，一个问题被划分为多个子问题。每个子问题都是单独解决的。最后，将子问题组合起来形成最终解决方案。

如下图所示，归并排序算法递归地将数组分成两半，直到我们达到具有 1 个元素的数组的情况。之后，merge 函数选取已排序的子数组并合并它们以逐渐对整个数组进行排序。

1. 图解

假设我们试图按升序对元素进行排序。

二、工作流程

归并排序是基于分而治之的思想实现的，拆开来说就两大步骤：

划分： 使用递归的方式将原数组划分成只有一个元素的子数组，这个一个元素就是已经排好序的了

治理： 将排好序的子数组按照规则合并以构建一个最终的排序数组

归并排序算法最重要的步骤就是合并，合并步骤是合并两个排序子数组以构建一个大的排序数组的解决方案。

编写合并函数的步骤

假设原数组是 arr[p..r] (p是第一个索引，r是最后一个索引)，q 是 p 和 r 之间的中间点，那么我们可以把原数组 arr[p..r] 拆分成两个子数组 arr[p..q] 和 arr[q+1..r]

合并函数的任务就是合并两个子数组 arr[p..q] 和 arr[q+1..r] 创建一个排序数组arr[p..r]，所以函数的输入是 arr、p、q 和 r

编写合并函数的步骤：

创建两个子数组分别是 arr[p..q] -> L 和 arr[q+1..r] -> M
将原数组的元素放到两个子数组中
创建三个指针 i，j，k
- i 指向第一个子数组 L 的索引，初始值为 0
- j 指向第二个子数组 M 的索引，初始值为 0
- k 指向原数组的索引，初始值为 p
遍历两个子数组，从中选择较小的元素，并将它们放到原数组的正确位置，直到到达任何一个子数组的末尾为止
将子数组的剩余元素放到原数组的末尾

代码实现如下：

// 合并子数组的元素到原数组
void merge(int arr[], int p, int q, int r) {

    // 创建两个子数组 L ← A[p..q] 和 M ← A[q+1..r]
    int n1 = q - p + 1;
    int n2 = r - q;

    int L[n1], M[n2];

    for (int i = 0; i < n1; i++)
        L[i] = arr[p + i];
    for (int j = 0; j < n2; j++)
        M[j] = arr[q + 1 + j];

    // 定义指针指向子数组和原数组的当前索引位置
    int i, j, k;
    i = 0;
    j = 0;
    k = p;


    // 遍历两个子数组，从中选择较小的元素，并将它们放到原数组的正确位置，
    // 直到到达任何一个子数组的末尾为止
    while (i < n1 && j < n2) {
        if (L[i] <= M[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = M[j];
            j++;
        }
        k++;
    }

    // 将子数组的剩余元素放到原数组的末尾
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = M[j];
        j++;
        k++;
    }
}
复制代码

Merge() 函数逐步解释

这个函数发生了很多事情，所以让我们举一个例子来看看它是如何工作的。

一图胜千言，假设原数组如下图：

数组 A[0..5] 包含两个排序的子数组 A[0..3] 和 A[4..5]. 让我们看看合并函数如何合并两个数组。

步骤 1：创建要排序的子数组的重复副本

// Create L ← A[p..q] and M ← A[q+1..r]
int n1 = q - p + 1 = 3 - 0 + 1 = 4;
int n2 = r - q = 5 - 3 = 2;

int L[4], M[2];

for (int i = 0; i < 4; i++)
    L[i] = arr[p + i];
// L[0,1,2,3] = A[0,1,2,3] = [1,5,10,12]

for (int j = 0; j < 2; j++)
    M[j] = arr[q + 1 + j];
// M[0,1] = A[4,5] = [6,9]
复制代码

步骤 2：维护子数组和主数组的当前索引

    
    int i, j, k;
    i = 0; 
    j = 0; 
    k = p; 
复制代码

第 3 步：直到我们到达 L 或 M 的末尾，在元素 L 和 M 中选取较小的元素并将它们放置在 A[p..r]

    while (i < n1 && j < n2) { 
        if (L[i] <= M[j]) { 
            arr[k] = L[i]; i++; 
        } 
        else { 
            arr[k] = M[j]; 
            j++; 
        } 
        k++; 
    }
复制代码

第 4 步：当我们用完 L 或 M 中的元素时，拿起剩余的元素并放入 A[p..r]

   // 将第一个数组中的剩余元素复制到主子数组
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }
复制代码

   // 将第二个数组的剩余元素复制到主子数组
    while (j < n2)
    {
        arr[k] = M[j];
        j++;
        k++;
    }
}
复制代码

三、代码实现

1. 伪代码实现

我们是否已到达任何子数组的末尾？
    不：
        比较两个数组的当前元素 
        将较小的元素复制到已排序的数组中
        移动包含较小元素的元素的指针
    是的：
        复制非空数组的所有剩余元素
复制代码

2. java 实现

import java.util.Arrays;

/**
 * 归并排序
 *
 * @className: MergeSort
 * @date: 2021/6/30 14:17
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = { 6, 5, 12, 10, 9, 1 };
        mergeSort(arr, 0, arr.length -1);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 递归调用，将原数组划分成子数组
     * @param arr 原数组
     * @param p 起始索引
     * @param r 结束索引
     */
    public static void mergeSort(int[] arr, int p, int r) {
        if (p < r) {
            int q = (p + r) /2;
            mergeSort(arr, p, q);
            mergeSort(arr, q + 1, r);
            merge(arr, p, q, r);
        }
    }

    public static void merge(int[] arr, int p, int q, int r) {
        // 定义两个子数组用来保存原数组的元素
        int n1 = q - p + 1;
        int n2 = r - q;
        int[] L = new int[n1];
        int[] M = new int[n2];
        // 将原数组的元素保存到子数组中
        for (int i = 0; i < n1; i++) {
            L[i] = arr[p + i];
        }
        for (int i = 0; i < n2; i++) {
            M[i] = arr[q + i + 1];
        }
        // 定义三个指针分别指向原数组和子数组的索引
        int i = 0;
        int j = 0;
        int k = p;
        // 遍历子数组的元素，直到到达子数组的末尾
        while (i < n1 && j < n2) {
            if (L[i] < M[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = M[j];
                j++;
            }
            k++;
        }
        // 将子数组剩余元素保存到原数组
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = M[j];
            j++;
            k++;
        }
    }
}
复制代码