归并算法
1.在解释算法优缺点的时候，首先要提到2点，一是比较的次数，二是数据要改变或移动的次数。第一个比较好理解，那什么叫改变和移动的次数呢？比如说2这个数据在存储上存储的是10，如果现在2变成4，那么存储就变成了100，这个过程需要将2向左移动一位，那么就叫移动一次，如果是2变成8，那么就需要移动2次。在实际运算过程中不会考虑这么细致。
2.归并算法是排序算法中的第五种，前四种依次是：冒泡，选择，插入，快速。
3.归并的核心思想是分治。分治顾名思义就是分开治理，假设一个问题，有若干个小问题组成，那么分治就是先逐个击破每个小问题。(有点解高中物理，数学题的感觉)
4.归并算法的解释语言解释：如果你在网上去找一些归并算法的资料学习，那么你可能要茫然到最后不得不靠着阅读代码才能真正理解。所以有必要正真的用文字来描述下归并的全过程，毕竟直接阅读代码是晦涩难懂的。
假设一组数据有8个，一开始将这8个数据两两一组分成4组，然后对每组进行排序，这个地方叫做分治。然后第二次是将8个数据分成两组，每组4个数据，其中这4个数据分别是前两个和后两个已经有序，所以接下来的处理就是按照从左到右的顺序一个一个取出两组有序数据比较排列成一个有序数组，这个数组有4个数据。另外一边4个数据也是同样操作。这样就得到了一个左边和右边都有4个有序数据的数组，再按照以上操作，将这两组数据归并。
5.java代码
package algorithm.merge;
public class Merge {
public static void main(String[] args) {
int[] a = new int[]{4, 3, 6, 1, 2, 5, 8, 7};
mergeSort(a, 0, 1);
for (int i = 0; i < a.length; ++i) {
System.out.print(a[i] + " ");
}
}
/**
* 目的是将两个有序列表归并成一个有序表,这是一个分治点
* start 第一个有序表的起始索引
* mid 第二个有序表的起始索引
* end 第二个有序表的结束索引
*/
public static void merge(int[] target,int start,int mid,int end){
int[] temp = new int[end-start+1];//一个临时数组，用来存储两个归并好的有序列表
int indexS = start;//第一个有序表的索引
int indexM = mid;//第二个有序表的索引
int indexT = 0;//temp数组的索引
//将两个有序表排列成一个有序表，直到其中的一个表数据取完，这时候将另一个表的剩余数据，一次添加到temp的尾部。
while(indexS<mid && indexM<=end){
if(target[indexS]<target[indexM]){
temp[indexT++] = target[indexS++];
}else{
temp[indexT++] = target[indexM++];
}
}
//如果第一个表还有数据
while(indexS<mid){
temp[indexT++] = target[indexS++];
}
//如果第二个表还有数据
while(indexM<=end){
temp[indexT++] = target[indexM++];
}
//将temp替换到原来target数组,从start的往后拷贝temp.length个数据
//这个arraycopy方法是native修饰的，也就是说这个方法是从内存上直接copy的，效率特别高
System.arraycopy(temp, 0, target, start, temp.length);
}
/**
* length 每次归并的列表长度，开始为1
* 从0开始,
* 下面的例子按照8个长度数组举例子
*/
public static void mergeSort(int[] target,int start,int length){
int size = target.length;//target数组总长度，用于计算分组数
//例如第一次归并长度为1，那么就需要将数组分为4组，每组2个数据归并，所以将length向左移1位，也就是乘以2
int group = size/(length<<1);//向下取整机制，假设是9个数，那么也是4组，就造成第9个数组未参与排序
//当length==8的时候，那么group就等于0，此时结束算法(递归结束);
if(group==0){
return;
}
//循环将group组数据归并
for(int i=0;i<group;++i){
int s = i * 2 * length;
//递归调用merge排序
//当i=0时候merge(target,0,1,2);
//当i=1时候merge(target,2,3,4);
//当i=2时候merge(target,4,5,6);
//当i=3时候merge(target,6,7,8);
//也就是说当分4组的时候，0-2，2-4，4-6，6-8被分治排序。
merge(target,s,s+length,(length<<1)+s-1);
}
//用总长度与每组长度取模运算，如果模为0代表数组的长度是2的整数次方，为最乐观情况下
//如果模不为0意味着每次结束的时候余下的数都要与前面所有的数进行一次归并。
//下面注释的代码为常规写法
// int mod = size%(length<<1);
// if(mod!=0){
// merge(target,0,(length<<1)*group,target.length-1);
// }
//下面这段代码功能用途和上面的完全相同
//这段代码运用的是&运算，效率上要高于注释的取模运算(神就在此处体现)
//此处的运算，只有当length是2的指数幂时，结果是对的，其他一律错，正好这个地方必然是2的指数幂。
int r = size & ((length << 1) - 1);
if (r != 0){
merge(target, size - r - 2 * length, size - r, size - 1);
}
mergeSort(target,0,length<<1);
}
}
6.思考的问题
a.当归并的数组长度不是2的指数次幂，是否可以通过补成2的指数次幂运算？
b.当归并的数组长度不是2的指数次幂，是否可以去掉多余的数，当其余的归并成功后再插入？
