1.将一个序列从中间位置分成两个序列；
2.在将这两个子序列按照第一步继续二分下去；
3.直到所有子序列的长度都为1，也就是不可以再二分截止。这时候再两两合并成一个有序序列即可。
下面的这张图片可以很清晰的解释该原理：
def merge(a, b): c = [] h = j = 0 while j < len(a) and h < len(b): if a[j] < b[h]: c.append(a[j]) j += 1 else: c.append(b[h]) h += 1 ? if j == len(a): for i in b[h:]: c.append(i) else: for i in a[j:]: c.append(i) ? return c ? ? def merge_sort(lists): if len(lists) <= 1: return lists middle = len(lists)//2 left = merge_sort(lists[:middle]) right = merge_sort(lists[middle:]) return merge(left, right) ? ? if __name__ == ‘__main__‘: a = [14, 2, 34, 43, 21, 19] print (merge_sort(a))
最坏时间复杂度 ：O(nlongn)
稳定性：稳定
参考链接：
原文：https://www.cnblogs.com/gengyufei/p/13279950.html