1. 目录

本节介绍两个最经典的排序算法之一的归并排序（另外个自然是快速排序了）

2.basic merge sort

将数列分成两份分别排序，然后最后再合并；这种分治思想递归的使用，就是归并排序了。

2.1 基本过程

基本过程如下：

2.2 实现

代码中的断言部分是为了方便调试用的。在运行程序的时候可以方便的开启或者关闭断言

注意点：不要在递归函数中使用辅助数组，频繁创建辅助数组会影响性能。

2.3 算法分析

根据提议得出比较次数的递归式

1. 采用推导

1. 采用归纳假设

2.4 in-place算法

定义如下：简单来说就是不需要额外的辅助内存空间的。(小于等于clogN的辅助空间仍然认为是in-place的)

2.5 归并排序优化

1. 对于较小的排列对象，只使用插入排序就可以了，代码中是定义了CUTOFF变量来判断，何时使用插入排序

1. 如果已经有序了，尽早返回

1. 合并时交换辅助数组和原数组的角色

原本合并时都是合并到原数组，现在合并合并到辅助数组，这样可以减少每次递归时的拷贝数据到辅助数组的操作！

3. bottom-up merge sort

自底向上的归并算法，可以观察下图的过程与之前basic merge sort的图的区别，自底向上一开始就将整体分成小的自序列不断地归并；而基本归并算法则先左边的归并，再右边的归并。虽然从最本质上来讲，他们的子操作都是归并小的自序列，只不过归并子序列的时序不同。（个人理解）

3.1 基本过程

3.1 实现

可以看到自底向上的归并排序实现上可以不采用递归，通过一个增量来控制递归子序列大小。 merge方法的代码和前面的相同

3.2 使用比较器comparator

3.3 稳定性

主要记住稳定的排序，剩下的就是不稳定的， 稳定的是冒泡、插入、基数、归并。缩写为IRMB（insert,radix,merger,bubble），“爱人民币”

插入排序：比较局部有序序列时候不移动相同的数，稳定
选择排序：选择最小的时候涉及交换，可能交换时导致相同的数之间的位置变化，不稳定
希尔排序：也存在跨距离的交换，因此不稳定
归并排序：判断大小时，相等不移动，不会改变相对位置

练习题：
要去除重复的点，下面那种方法不好，第三种方法不好，因为最后Y坐标用快排会导致相同坐标的点分开：

例如：归并后如下
(1,8)
(2,8)
(2,8)
快排后可能如下：
(2,8)
(1,8)
(2,8)

4. 编程作业

这次的作业是共线问题。题目见：题目说明
其他参考资料1
其他参考资料2

题目要求用暴力破解，和基于排序的方法来处理；暴力破解的性能自然是比较差的

总结要点：

1. 点需要进行编号，按照编号遍历
2. 避免共线线段的重复计算，例如a->b->c->d和b->c->d