02 算法推送--归并排序
注：由于考虑到上两周同学们都有三门以上的期中考试，为了帮助同学们更好地复习期中考（绝对不是作者也在复习期中），本系列断更了一期。考虑到各种不确定因素，要不以后就改成不定期更新了吧（暴论x）
0.上周思考题
你在考场上绞尽脑汁地思考着这题：“我不知道最优情况下的路标设置，因此很难正面直接求出相邻路标间的最大距离……”
突然邻桌的同学啪地一声就站起来了，很快啊！然后上来就大喊一声：“思考题的答案是37！”
考场的老师大意了啊，没拦住，同学们百脸懵逼，只有你冷静下来仔细思考：“他说的答案是最优的吗？”
要验证这个答案是不是最优的，理论上我们得证明两件事：①存在一种方案能使得这个最小距离存在②不管用什么方案，这个距离都不可能更小了
事实上我们很容易解决第一个问题：如果我们只要使得每两块相邻的石头之间距离不大于37，那么很容易想到，每隔37的距离放一块石头一定是最优的……这就意味着，我能在O(n)的时间内去验证37是否可行。
“太棒了！我只要对于每一个距离都用这样的方法去检验一遍，那么最小的检验成功的距离就是最后的答案！”，你这样想。但是理性告诉你，如果你对每一个距离都去检验一遍，那么这和“考场上有一千万名同学（如果有这么多人）站起来依次报出不同的答案，然后你一个个去检验”有什么区别呢？
临近下考，你在极度愤怒的情况下突然想起了上次推送的标题——“二分！”……
注：
①由于我知道当假定距离为x时，存在这样的方案，那么答案就一定会小于等于x，类似于上一次推送的方法，我们可以在进行O(logL)个检验后就得到答案。结合我们使用一次检验的复杂度是O(n)，故我们解决这道题目的总体复杂度是O(nlogL)
②这个方法被算法竞赛选手称为“二分答案”，顾名思义就是对答案进行二分。这其实是对二分方法的一种拓展：二分不仅可以用作“序列上查找”，它还能在答案轴上二分、在时间轴上二分、一堆问题一起在答案轴上二分、一堆操作一起在时间轴上二分……
③上述的几种方法在算法竞赛中分别称为：“二分答案”、N/A、“整体二分”、“时间轴分治/CDQ分治”。感兴趣的同学可以自行搜索了解。
引入（归并排序）
张三是T大微积分A课程的一名助教。由于工（张）作（三）量（在）巨（摸）大（鱼），他连熬了几天夜才判完全班的卷子。现在，筋疲力尽的张三终于得到了300名同学的成绩。不过还有最后一个问题：老师让他把成绩排序之后再发过去。然而张三只有一台祖传的土豆电脑，需要1秒才能完成一次普通的运算。同时，土豆电脑很不稳定，时刻需要张三在边上守着。张三只会冒泡排序算法，这意味着他要在电脑前等待几万秒。张三考虑到自己已经好几天没合眼了，就找到了你，让你提供一种高速的排序算法，在一个小时内解决问题，以防止自己在等待时猝死。由于你20分的平时分完全取决于张三的脸色，你高（被）兴（迫）地接下了这个工作……
一、 回顾程设作业
二、 设计排序算法
SORT (LEFT, RIGHT)
//将序列从LEFT号元素到RIGHT号元素排序
{
MID=(LEFT+RIGHT)/2 //找到序列中间点
SORT (LEFT, MID) //给左半部分排序
SORT (MID+1, RIGHT) //给右半部分排序
MERGE (LEFT, RIGHT) //将两部分合并成答案（与作业题方法相同）
}
三、 思考题