归并排序和快排都使用了分治思想，可以借鉴这种思想来解决非排序问题，比如：如何在的时间复杂度内找到一个无序数组中的第k大元素？
归并排序原理
归并排序思想：将数组从中间分为前后两部分，然后对前后两部分分别排序，再将排好序的部分合并。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。分治算法一般都是用递归来实现的。
归并排序稳不稳定关键是看merge函数，即将两个有序子序列组合成一个有序序列的函数。我们可以将子序列按照原来的顺序进行合并，这样就可以保证值相同的元素在合并前后的相对顺序不变，所以归并排序是一个稳定的排序算法。
归并排序的最好、最坏、平均时间复杂度均为，非常稳定，与原始数组的有序程度无关。但是归并排序没有像快排那样应用广泛为什么呢？因为归并排序的空间复杂度不是。
归并排序需要创建一个临时空间来存放新顺序的序列，尽管每次合并操作都会申请额外的内存空间，但是在合并完成之后，临时开辟的内存空间就被释放了，所以任意时刻CPU只会有一个函数在执行，即只有一个临时的内存空间在使用，所以空间复杂度为。
