学习动机

归并排序会把问题拆分成更小的子问题，分别解决，然后合并结果。合并这一步，也就是合并两个已经排好序的列表，是这个算法的核心。

为什么要学习归并排序？

• 快速且稳定可预测：在最佳、平均和最坏情况下，它的运行时间都是 O(n log n)。
• 稳定：相等的元素会保持原有的相对顺序。
• 适合处理大型数据：当数据无法全部放入内存时（外部排序），以及处理链表时，它都表现良好。
• 分而治之：它能帮助你学习一种广泛应用于许多高级算法的模式。