归并排序 Merge Sort

归并排序是一个高效的、基于比较的排序算法。

原理

归并排序是一个典型的分治(Divide and Conquer)算法。具体思路如下：

• 将未排序的序列分割成 n 个只有单个元素的子序列。（单个元素的序列认为是有序的）
• 重复的将各个子序列合并成新的有序的序列，直到只有一个序列即为排好序的序列。

图示

可以通过动画演示理解, 以下网上找的两个动画。如果你想操作不同的参数来演示，可以上这个网站visualgo.net动手试试。