之前说过了quick sort，提到了他里面用到的divide and conquer 的思路。用类似思路做sort的，最典型的就是merge sort。

merge sort的思路大概如下：把数组一直往下拆分，每次拆分成2部分，直到每个部分里只有一个element，然后再往回把2个部分merge回去，每一个部分里都是sorted，每次merge的步骤就是把2个sorted的部分，merge成一个。最后当返回最上层的时候，整个的array就是sorted了。

举个例子。比如说我们有[5, 3, 2, 4]

第一步拆分成2个部分: [5, 3], [2, 4]

对每一个部分继续拆分：

[5, 3] -> [5], [3]

[2,4] -> [2], [4]

每个部分都只有一个element了，无法继续拆分。现在我们把它往回merge回去。

[5], [3] -> merge 两个sorted array，[3, 5]

[2], [4] -> [2,4]

还没回到最初一层，继续merge这两个已经sorted的array：

[3, 5], [2,4] -> [2, 3, 4, 5]

已经merge了整个array，算法结束。

每次merge两个sorted的array部分的时间复杂度是n，recursive的往下divide再merge回来的流程是logn，所以最后的时间复杂度是nlogn.

这里我们只是浅谈了merge sort的算法思路，以后有机会再具体说说这个算法怎么实现。