归并排序和快速排序，时间复杂度为O(nlogn)，适用于较大规模数据的排序。
采用分治思想。

归并排序（Merge Sort）

归并排序的核心思想还是蛮简单的。如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。
image.png
归并排序使用的就是分治思想。分治思想跟我们前面讲的递归思想很像。是的，分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧，

用递归的方式来实现归并排序

如何写递归代码
1.写出递推公式
2.找到终止条件
3.将递推公式翻译成代码

  2. 递推公式：
  3. merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r));
  5. 终止条件：
  6. p >= r 不用再继续分解

merge_sort(p…r) 表示，给下标从 p 到 r 之间的数组排序。我们将这个排序问题转化为了两个子问题，merge_sort(p…q) 和 merge_sort(q+1…r)，其中下标 q 等于 p 和 r 的中间位置，也就是 (p+r)/2。当下标从 p 到 q 和从 q+1 到 r 这两个子数组都排好序之后，我们再将两个有序的子数组合并在一起，这样下标从 p 到 r 之间的数据就也排好序了。

  2. // 归并排序算法, A是数组，n表示数组大小
  3. merge_sort(A, n) {
  4.   merge_sort_c(A, 0, n-1)
  5. }
  7. // 递归调用函数
  8. merge_sort_c(A, p, r) {
  9.   // 递归终止条件
  10.   if p >= r  then return
  12.   // 取p到r之间的中间位置q
  13.   q = (p+r) / 2
  14.   // 分治递归
  15.   merge_sort_c(A, p, q)
  16.   merge_sort_c(A, q+1, r)
  17.   // 将A[p...q]和A[q+1...r]合并为A[p...r]
  18.   merge(A[p...r], A[p...q], A[q+1...r])
  19. }

merge(A[p…r], A[p…q], A[q+1…r]) 这个函数的作用就是，将已经有序的 A[p…q]和 A[q+1….r]合并成一个有序的数组，并且放入 A[p….r]。

和合成两个有序链表的思路一致，首选申请一个两个数组长度之和的数组，用两个指针分别指向两数组的第一个元素进行比较，小者存入新申请的数组中，并且指针进行后移，在于另一个数组的元素进行比较。比完之后还有剩余空间的数组就追加到数组后面即可完成。

归并排序的性能分析

第一，归并排序是稳定的排序算法吗？

是的。归并排序采用分治思想，将数组先分解，在合并。我们只需要在合并的时候，保证分解前一个数组在合并时也在前面。就可以保证相同的元素在排序前后的顺序时不变的。

第二，归并排序的时间复杂度是多少？

递归