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

归并排序（Merge Sort） - 图1
合并排序示例

分而治之策略

使用分而治之的技术，我们将问题划分为子问题。当每个子问题的解决方案准备就绪时，我们“组合”子问题的结果来解决主要问题。假设我们必须对一个数组进行排序 一. 一个子问题是从索引开始对这个数组的一个子部分进行排序磷 并在索引处结束 r，记为 A[p..r].

Divide
如果 q 是 p 和 r 的中间点，那么我们可以将子数组 A[p..r] 拆分为两个数组 A[p..q] 和 A[q+1, r]。

Conquer
在Conquer步骤中，我们尝试对子数组 A[p..q] 和 A[q+1, r] 进行排序。如果我们还没有达到基本情况，我们再次划分这两个子数组并尝试对它们进行排序。

Combine
当Combine步骤到达基本步骤时，并且我们得到数组 A[p..r] 的两个排序子数组 A[p..q] 和 A[q+1, r] 时，我们通过创建一个排序数组 A 来合并结果[p..r] 来自两个已排序的子数组 A[p..q] 和 A[q+1, r]。

归并排序算法

MergeSort 函数反复将数组分成两半，直到我们尝试对大小为 1 的子数组执行 MergeSort，即 p == r。之后，merge 函数开始发挥作用，将排序后的数组组合成更大的数组，直到合并整个数组。

  1. MergeSort(A, p, r):
  2.     if p > r 
  3.         return
  4.     q = (p+r)/2
  5.     mergeSort(A, p, q)
  6.     mergeSort(A, q+1, r)
  7.     merge(A, p, q, r)

要对整个数组进行排序，我们需要调用 MergeSort(A, 0, length(A)-1)。如下图所示，归并排序算法递归地将数组分成两半，直到我们达到具有 1 个元素的数组的基本情况。之后，merge 函数选取已排序的子数组并合并它们以逐渐对整个数组进行排序。

归并排序（Merge Sort） - 图2
合并排序

图解归并步骤

每个递归算法都依赖于一个基本案例和结合基本案例结果的能力。归并排序也不例外。归并排序算法最重要的部分是，你猜对了，归并步骤。合并步骤是对合并两个排序列表（数组）以构建一个大排序列表（数组）的简单问题的解决方案。该算法维护三个指针，一个用于两个数组中的每一个，另一个用于维护最终排序数组的当前索引。

  1. Have we reached the end of any of the arrays?
  2.     No:
  3.         Compare current elements of both arrays 
  4.         Copy smaller element into sorted array
  5.         Move pointer of element containing smaller element
  6.     Yes:
  7.         Copy all remaining elements of non-empty array
归并排序（Merge Sort） - 图3
合并步骤

算法的伪码

我们上面描述的合并步骤与我们用于合并排序的合并步骤之间的一个显着区别是我们只对连续的子数组执行合并功能。
这就是为什么我们只需要数组，第一个位置，第一个子数组的最后一个索引（我们可以计算第二个子数组的第一个索引）和第二个子数组的最后一个索引。我们的任务是合并两个子数组 A[p..q] 和 A[q+1..r] 以创建一个排序数组 A[p..r]。所以函数的输入是 A、p、q 和 r。

合并函数的工作原理如下：

  1. 创建子数组 L ← A[p..q] 和 M ← A[q+1..r] 的副本。
  2. 创建三个指针 i, j 和 k
    1. i 保持当前的索引 L，从 1 开始
    2. j 维护 M 的当前索引，从 1 开始
    3. k 维护 A[p..q] 的当前索引，从 p 开始。
  3. 直到我们到达 L 或 M 的末尾，从 L 和 M 中选择较大的元素并将它们放置在 A[p..q] 的正确位置
  4. 当我们用完 L 或 M 中的元素时，拿起剩余的元素并放入 A[p..q]
// Merge two subarrays L and M into arr
void merge(int arr[], int p, int q, int r) {

    // Create L ← A[p..q] and 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];

    // Maintain current index of sub-arrays and main array
    int i, j, k;
    i = 0;
    j = 0;
    k = p;

    // Until we reach either end of either L or M, pick larger among
    // elements L and M and place them in the correct position at 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++;
    }

    // When we run out of elements in either L or M,
    // pick up the remaining elements and put in A[p..r]
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

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

Merge() 函数的图解

这个函数发生了很多事情，所以让我们举一个例子来看看它是如何工作的。
像往常一样，一图胜千言。

归并排序（Merge Sort） - 图4
合并数组的两个连续子数组

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

void merge(int arr[], int p, int q, int r) {
// Here, p = 0, q = 4, r = 6 (size of array)
  • 步骤 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]
归并排序（Merge Sort） - 图5
创建子数组的副本以进行合并
  • 步骤 2：维护子数组和主数组的当前索引
    int i, j, k;
    i = 0; 
    j = 0; 
    k = p;
归并排序（Merge Sort） - 图6
维护子数组和主数组副本的索引
  • 第 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++; 
    }
归并排序（Merge Sort） - 图7
比较已排序子数组的各个元素，直到我们到达一个结尾
  • 第 4 步：当我们用完 L 或 M 中的元素时，拿起剩余的元素并放入 A[p..r]
    // We exited the earlier loop because j < n2 doesn't hold
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }
归并排序（Merge Sort） - 图8
将第一个数组中的剩余元素复制到主子数组 
    // We exited the earlier loop because i < n1 doesn't hold  
    while (j < n2)
    {
        arr[k] = M[j];
        j++;
        k++;
    }
}
归并排序（Merge Sort） - 图9
将第二个数组的剩余元素复制到主子数组

如果 M 的大小大于 L，则需要此步骤。在合并函数的最后，子数组 A[p..r] 排序。

算法的实现

// Merge sort in Java

class MergeSort {

  // Merge two subarrays L and M into arr
  void merge(int arr[], int p, int q, int r) {

    // Create L ← A[p..q] and M ← A[q+1..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 j = 0; j < n2; j++)
      M[j] = arr[q + 1 + j];

    // Maintain current index of sub-arrays and main array
    int i, j, k;
    i = 0;
    j = 0;
    k = p;

    // Until we reach either end of either L or M, pick larger among
    // elements L and M and place them in the correct position at 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++;
    }

    // When we run out of elements in either L or M,
    // pick up the remaining elements and put in A[p..r]
    while (i < n1) {
      arr[k] = L[i];
      i++;
      k++;
    }

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

  // Divide the array into two subarrays, sort them and merge them
  void mergeSort(int arr[], int l, int r) {
    if (l < r) {

      // m is the point where the array is divided into two subarrays
      int m = (l + r) / 2;

      mergeSort(arr, l, m);
      mergeSort(arr, m + 1, r);

      // Merge the sorted subarrays
      merge(arr, l, m, r);
    }
  }

  // Print the array
  static void printArray(int arr[]) {
    int n = arr.length;
    for (int i = 0; i < n; ++i)
      System.out.print(arr[i] + " ");
    System.out.println();
  }

  // Driver program
  public static void main(String args[]) {
    int arr[] = { 6, 5, 12, 10, 9, 1 };

    MergeSort ob = new MergeSort();
    ob.mergeSort(arr, 0, arr.length - 1);

    System.out.println("Sorted array:");
    printArray(arr);
  }
}

算法复杂度

时间复杂度
最好的 O(n*log n)
最差 O(n*log n)
平均 O(n*log n)
空间复杂度 O(n)
稳定 是的

时间复杂度

最佳情况复杂度： O(nlog n)
最坏情况复杂度： O(nlog n)
平均情况复杂度： O(n*log n)

空间复杂度

归并排序的空间复杂度为 O(n)..

算法的应用

  • 倒数问题
  • 外部排序
  • 电子商务应用

相似的算法

  1. 快速排序
  2. 插入排序
  3. 选择排序
  4. 桶排序