归并排序

做法

归并，基于分治，但是不同于快排

1.确定分界点，这回的分界点是固定的，是mid。=

2.排序左边和右边

3.归并

如图，红色箭头是该区间的最小值，假设答案数组res[]。如果A数组最小值比B数组最小值还小，把该值放入res[]。然后箭头向右移一位。继续这样比较

一个区间全部值取完了，一个数组剩下的值直接放入res[]后面即可。因为A数组最后一个数肯定比B数组剩下的数的开头的那个数要小，所以B剩下的所有数都是大于A最后一个数的，故没有影响

 举例

A={1,3,5,7,9}

B={2,4,5,8,10}

（举例时最好设置多几个相同的值，便于一般性）

先取1，然后取2,3,4，到5了，我们发现先取哪个都没事，所以继续，5（假设取的是A）,5（B），7,8,9,10

举不举都差不多了，很好理解，并不是很抽象

但是从这里我们发现，这个排序是稳定的！因为每次都是有限考虑取A，后取B，所以不会改变数列顺序

时间复杂度

 递归先是n，再是一半，再是一半的一半

n什么时候除到1？那就是log n层，n为1啦

一共长度为n

所以时间复杂度为（nlogn），100%不会变动

 代码