归并排序核心思想
- 如果要排序一个数组，先把数组从中间分成前后2部分，然后对前后两部分分别排序，再将排序好的两部分合在一起，这样整个数组就有序了。
- 归并排序使用的是分治思想，将大问题划分成小的子问题来解决。注意，分治是一种解决问题的处理思想；递归是一种编程技巧。
归并排序性能分析
- 归并排序可以是一个稳定的排序算法，这个主要看2个数组的合并排序函数。
- 归并排序的时间复杂度（O(nlogn)）
假设对n个元素进行归并排序需要的时间是T(n)，那分解成两个子数组排序的时间都是T(n/2)。已知，合并两个有序子数组的时间复杂度是O(n)。所以归并排序的时间复杂度计算公式为：
T(1) = C； n=1 时，只需要常量级的执行时间，所以表示为 C。
T(n) = 2*T(n/2) + n； n>1
= 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
= 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
= 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
......
= 2^k * T(n/2^k) + k * n
......
当T(n/2^k) = T(1)时，n/2^k=1，得k=log2n。将k带入公式得到T(n)=Cn+n*log2n。用大O计数法表示，T(n)=O(nlogn) 所有情况下。 - 归并排序的空间复杂度（O(n)）
归并排序的合并函数，在合并两个有序数组时需要借助额外存储空间，递归代码的空间复杂度不能像时间复杂度那样累加；尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大不会超过n个数据的大小，所以空间复杂度是O(n)。
快排核心思想
- 如果要对数组排序，从数组中选任意一个数据作为分区点pivot，然后遍历数组的所有数据，将小于pivot的放到其左侧，大于pivot的放到其右侧，这样一次遍历后，pivot找到了自己所应处于的位置；pivot将原数组分成了3部分，其左侧都小于它，右侧都大于它，对其左右侧再进行定分区点分区操作，直到所有的点都找到其应处于的位置。
快排性能分析
- 分区操作可以原地完成（最后交换分区点的位置），所以它的空间复杂度是O(1)；当然也可以借助额外内存空间。
- 快排不是一个稳定的排序算法。
- 大多情况下时间复杂度都可以做到O(nlogn)，极端情况（使用尾元素做分区点并且数组本就是有序的）会退化成O(n²)。
