快排算法与归并算法时间复杂度都是O(nlogn)的排序算法。适合大规模的数据排序。
思想利用的是分治思想。

归并排序

原理

原理：排序一个数组，把数组从中间分为两部分，然后对前后两部分进行分别排序。最后把排序好的两部分都合并在一起，在合并的时候也会进行排序。就是排序好的数据

摘自极客时间

合并：在合并的过程中会申请一个临时数组空间，然后把两个排序号的数组进行取值对比，哪个小放入到临时数组中。
思路：
两个数组数据在比较大小的时候，可能存在一个数组中的数据有剩余的。需要把剩余的数据也迁移到临时数组中

摘自极客时间

思考借助哨兵的减少代码的量级。

性能分析

稳定算法？

稳定算法：值相同的元素不需要移动。
在归并算法中，数据相等元素在合并之后的算法中先把前半部分的数据放到临时数组中，这样保证了值等同的元素，在合并前后顺序不变。所以稳定算法。

时间复杂度

合并两个子集合操作时间复杂度是O(N)
推导公式是用

T(n) = 2*T(n/2) + n
        = 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
        =2^k *T(n/2^k) +k *n 

其中n是执行合并需要的时间。
当n/2^k ==1 的时候。可以计算出k的值。T(n)=Cn+n*log2(n)。大O标记法就是O(nlogn)
最好，最坏，平均都是这个时间复杂度

空间复杂度

不是原地排序算法。
原地排序算法需要空间复杂度是O(1),归并排序在实现的过程中需要申请临时空间。内存大小最大为数据的长度n，所以空间复杂度是O(n)

快排

快排思想：排序数据下标从a-p,那么选择从a-p之间的任意数据作为pivot分区点。
遍历数据，将小于分区点的值放到左边，大于分区点的值放到右边。

等待java代码的实现

分区
交换数据

性能分析

也是分区操作计算公式同归并算法。时间复杂度是O(nlogn)，大会最坏的情况下时间复杂度会扩展到O(n*n)，
选择的分区点最小，导致没有成功的分区。

稳定算法

数据相等的时候不进行操作数据移动。所以是稳定算法

时间复杂度

O(nlogn)最坏是O(nlogn)

空间复杂度

因为是数据交换，所以没有使用到多余的空间。是原地排序算法