摄影：产品经理厨师：kingname
请确保你已经看了我昨天的公众号文章。昨天的内容是今天的基础。
一日一技：在 Python 里面如何合并多个有序列表并使得结果依然有序？
在昨天的文章里面，我们已经知道，可以使用 heapq.merge把两个有序列表合并成新的有序列表。
现在，我们来设计一个排序算法，对列表：[1,4,2,0,4,5,1,-3,-8,188,34] 进行排序。
我们现在先把列表拆分成a列表：[1,4,2,0,4,5]和b列表 [1,-3,-8,188,34]。如果我们能够分别让这两个列表各自有序，然后应用昨天的方法，合并一下，最终结果自然就出来了。
那么如何让这两个列表各自有序呢？我们以 [1,4,2,0,4,5]为例。继续把它拆分为两个列表 [1,4,2]和 [0,4,5]。只要这两个列表各自有序，那么合并一下就行了。
我们再来看 [1,4,2]，如何让它有序呢？我们继续分成两个列表 [1]和 [4,2]。显然只有一个元素的列表 [1]是有序的。
再来看 [4,2]，继续分成两个列表 [4]和 [2]。这两个列表都只有一个元素，所以他们都是有序的。此时对他们进行合并，得到 [2,4]。
[1] 与 [2,4]合并，得到 [1,2,4]。
[1,2,4]与 [0,4,5]合并，得到 [0,1,2,4,4,5]。
[0,1,2,4,4,5]与 [-8,-3,1,34,188]合并，得到 [-8,-3,0,1,1,2,4,4,5,34,188]。
排序完成。
整个过程先拆分再合并，这种排序算法叫做 归并算法。它的时间复杂度始终是 O(nlogn)。而我们常常听说的快速排序，只有在最好的情况下时间复杂度才能达到 O(nlogn)。所以归并排序在时间复杂度这个角度是优于快速排序的。
那么如何使用代码来实现呢？合并的部分请看昨天的文章，今天我们主要描述拆分的逻辑：
import heapq def sort(target): if not target: return [] if len(target) == 1: return target left = target[:len(target) // 2] right = target[len(target)//2 :] sorted_left = sort(left) sorted_right = sort(right) result = heapq.merge(sorted_left, sorted_right) return result
运行效果如下图所示：
