归并排序·MergeSort

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

若将两个有序表合并成一个有序表，称为二路归并。

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

算法原理

递归分割序列,比较合并已排序序列

  1. 把长度为 n 的输入序列分成两个长度为 n/2 的子序列；
  2. 对这两个子序列分别采用归并排序；
  3. 将两个排序好的子序列合并成一个最终的排序序列。

算法演示

// 归并排序
array:  [6] [3] [9] [4] [7] [1] [5] [2] [8] [0]
         ─────────────────   ─────────────────
        [6] [3] [9] [4] [7] [1] [5] [2] [8] [0]
         ─────   ─────────   ─────   ─────────
        [6] [3] [9] [4] [7] [1] [5] [2] [8] [0]
         ─────   ─────────   ─────   ─────────
        [6] [3] [9] [4] [7] [1] [5] [2] [8] [0]
         ─────   ─   ─────   ─────   ─   ─────
        [3] [6] [9] [4] [7] [1] [5] [2] [0] [8]
         ─────   ─────────   ─────   ─────────
        [3] [6] [4] [7] [9] [1] [5] [0] [2] [8]
         ─────────────────   ─────────────────
        [3] [4] [6] [7] [9] [0] [1] [2] [5] [8]
         ─────────────────────────────────────
        [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

// 归并排序结束

算法分析

时间复杂度

空间复杂度

稳定性

稳定排序算法

代码实现

参考