算法：归并排序（MergeSort）

1. 基本原理

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

2. 动画展示

3. 代码示例

4. 特性分析

• 归并排序不是原址操作；
• 时间复杂度：~O(nlogn)； 注：最多遍历logn趟，每一趟的时间复杂度是O(n)；
• 空间复杂度：~O(n)；
• 算法稳定性：稳定；