前言

合并排序（归并排序）是一种高效的排序算法，可以产生稳定的排序，这意味着如果两个元素具有相同的值，则它们在排序序列中的相对位置与它们在输入中的相对位置相同。

换句话说，具有相等值的元素的相对顺序保留在排序序列中。合并排序是一种比较排序，这意味着它可以对定义了小于关系的任何输入进行排序。

与快速排序一样，合并排序是一种分治算法。它将输入数组分成两半，为这两半调用自身，然后合并两半。

merge() 函数用于合并两半。merge(arr, l, m, r) 是一个关键过程，它假设 arr[l..m] 和 arr[m 1..r] 已排序，并将两个排序后的子数组合并为一个。

上图来自维基百科，显示了示例数组 {38、27、43、3、9、82、10} 的完整合并排序过程。如果我们仔细看这个图，我们可以看到数组被递归地分成两半，直到大小变为 1。一旦大小变为 1，合并过程开始动作并开始合并数组，直到完整的数组合并。

Java示例

import java.util.Arrays;
 
class Main
{
    // 合并两个排序的子数组 arr[low … mid]、 arr[mid 1 … high]
    public static void merge(int[] arr, int[] aux, int low, int mid, int high)
    {
        int k = low, i = low, j = mid   1;
 
        while (i <= mid && j <= high)
        {
            if (arr[i] <= arr[j]) {
                aux[k  ] = arr[i  ];
            }
            else {
                aux[k  ] = arr[j  ];
            }
        }
 
        // 复制剩余的元素
        while (i <= mid) {
            aux[k  ] = arr[i  ];
        }
 
        // 无需复制下半部分（因为剩下的项目已在辅助数组中处于正确位置）
        // 复制回原始数组
        for (i = low; i <= high; i  ) {
            arr[i] = aux[i];
        }
    }
 
    // 排序数组 arr[low…high]、 辅助数组 aux
    public static void mergesort(int[] arr, int[] aux, int low, int high)
    {
        if (high == low) {        // if run size == 1
            return;
        }
 
        // 找到中点
        int mid = (low   ((high - low) >> 1));
 
        // 递归地将数组运行分成两半，直到运行大小=1，然后合并它们
        mergesort(arr, aux, low, mid);          // 拆分/合并左半部分
        mergesort(arr, aux, mid   1, high);     // 拆分/合并右半部分
 
        merge(arr, aux, low, mid, high);        // 合并
    }
 
    // 检查arr是否按升序排序
    public static boolean isSorted(int[] arr)
    {
        int prev = arr[0];
        for (int i = 1; i < arr.length; i  )
        {
            if (prev > arr[i])
            {
                System.out.println("MergeSort Fails!!");
                return false;
            }
            prev = arr[i];
        }
 
        return true;
    }
 
    public static void main(String[] args)
    {
        int[] arr = { 12, 3, 18, 24, 0, 5, -2 };
        int[] aux = Arrays.copyOf(arr, arr.length);
        System.out.println("排序前：");
        System.out.println(Arrays.toString(arr)); 
        // 使用辅助数组'aux'对数组'arr'进行排序
        mergesort(arr, aux, 0, arr.length - 1);
 
        if (isSorted(arr)) {
            System.out.println("排序后：");
            System.out.println(Arrays.toString(arr));
        }
    }
}

输出：

排序前 
[12, 3, 18, 24, 0, 5, -2] 
排序后 
[-2, 0, 3, 5, 12, 18, 24]

性能

归并排序的最坏情况时间复杂度是O(n.log(n))，其中n是输入的大小。递归关系为：

T(n) = 2T(n/2) cn = O(n.log(n))

递归基本上总结了合并排序算法 - 对原始列表一半大小的两个列表进行排序，并添加n合并结果两个列表所采取的步骤。

归并排序算法所需的辅助空间是调用堆栈的O(n)。

缺点：

• 对于较小的任务，与其他排序算法相比速度较慢。
• 合并排序算法需要额外的 0(n) 内存空间用于临时数组。
• 即使数组是已经排序过的，也会经历整个过程。

本文出至：学新通技术网