总结: 归并排序, 快速排序 时间复杂度 O(nlogn).

冒泡排序、插入排序、选择排序这三种排序算法，它们的时间复杂度都是 O(n2)，比较高，适合小规模数据的排序。今天，我讲两种时间复杂度为 O(nlogn) 的排序算法，归并排序和快速排序。这两种排序算法适合大规模的数据排序，比上一节讲的那三种排序算法要更常用。
归并排序和快速排序都用到了分治思想，非常巧妙。我们可以借鉴这个思想，来解决非排序的问题，比如：如何在 O(n) 的时间复杂度内查找一个无序数组中的第 K 大元素？ 这就要用到我们今天要讲的内容。

1. 归并排序

// 归并排序算法, A是数组，n表示数组大小
merge_sort(A, n) {
        merge_sort_c(A, 0, n-1)
}

// 递归调用函数
merge_sort_c(A, p, r) {
        // 递归终止条件 
        if p >= r then return 

        // 取p到r之间的中间位置q 
        q = (p+r) / 2  // p+q溢出，改为 p + (q-p)/2
        // 分治递归 
        merge_sort_c(A, p, q) 
        merge_sort_c(A, q+1, r) 
        // 将A[p...q]和A[q+1...r]合并为A[p...r] 
        merge(A[p...r], A[p...q], A[q+1...r])
}

归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是 O(nlogn)。
归并排序的时间复杂度任何情况下都是 O(nlogn)，看起来非常优秀。但是，归并排序并没有像快排那样，应用广泛，这是为什么呢？因为它有一个致命的“弱点”，那就是归并排序不是原地排序算法。这是因为归并排序的合并函数，在合并两个有序数组为一个有序数组时，需要借助额外的存储空间。
在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)。

2. 快速排序

内容总结自：
极客时间：《数据结构与算法》王争, 12 | 排序（下）：如何用快排思想在O(n)内查找第K大元素？