排序算法二（快排，合并）

现在依旧很清晰记得大二时候学习快速排序时，总是没有办法梳理清晰，当时为了应付考试只能硬着头皮把算法的过程记住，考试的时候总是还会忘记，没有掌握快排的原理。前段时间，闲来无事，自己再回顾了一下教科书上的快速排序，发现教科书写得有些晦涩难懂，还是有些摸棱两可。今天正好把当年的痛处再来总结一把。

快速排序和合并排序，这两种排序都使用了分区治理的思想。

合并排序：把一个大的数据集拆分成各个小的数据集，当拆分到单个数据集时，再使用合并规则来两两合并，变成一个有序的数据集。其重点落在合并逻辑上，就是把两个有序的集合合并成为一个集合。

合并排序：不属于原地排序，属于稳定排序，时间复杂度为O(nlogn)

快速排序：把一个大的数据集拆分成小的数据集，每次拆分都有一个拆分点，拆分点左边的数据都小于拆分点值，拆分点右边的数据都大于拆分点值。然后不停拆分，直到单个数据集。其重点落在拆分过程，与合并排序正好相反。

快速排序：属于原地排序，但是不属于稳定排序，最坏时间复杂度为O(n^2)，平均时间复杂度为O(nlogn)。

show me code:

合并排序：

快速排序：