归并排序

一句话理解

归并排序：对半分，排好再合并两个有序数组。

为什么要学

稳定，最坏也是 n log n，求逆序对要用它。

讲解

合并时谁小取谁。需要临时数组。时间 O(n log n)，空间 O(n)。

例子

[3,1,4,2] 分成 [3,1] 和 [4,2]，排成 [1,3]、[2,4]，合并成 [1,2,3,4]。

常见错误

• 合并时漏拷贝某一侧剩余元素。
• mid 划分写错导致无限递归。