归并排序是分而治之算法策略的典型代表之一
分而治之算法的思路：
分而治之三步骤：分解原问题，解决子问题，合并问题解
1.分解原问题：将原问题分解为若干个规模较小，相对独立，与原问题形式相同的子问题。
2.解决子问：若子问题规模较小且易于解决时，则直接解。否则，递归地解决各子问题。
3.合并：将各子问题的解合并为原问题的解。
归并排序：
以数组为例，假设数组长度为n
1.首先把其拆分n组每组一个，
2.然后每相连的两组进行比较，并排序；
（第一遍排序之变成了n/2组，每组为2个，当然若n为奇数，则最后一组只有一个元素；）
3.继续执行2，直到排序后只有一组。
它的时间复杂度是O(nlogn).
java完整代码（递归实现）：
public void toMergeSort(int []arr,int left,int right) {
//递归出口
if(left >= right) {
return;
}
int mid = (int)((left+right)/2);
toMergeSort(arr,left,mid); //先左边递归
toMergeSort(arr,mid+1,right); //再右边递归
toSort(arr,left,mid,right); //调用排序函数
}
public void toSort(int []arr,int left,int mid, int right) {
int i = left ,j = mid+1 ,tempIndex = left; //i指向左半边，j指向右半边
int []tempArr = arr.clone();
while(i <= mid && j <= right) {
if(tempArr[i]>tempArr[j]) {
arr[tempIndex] = tempArr[j];
j++;
tempIndex++;
}
else {
arr[tempIndex] = tempArr[i];
i++;
tempIndex++;
}
}
while(i<=mid) {
//左边还没有完，右边已完
arr[tempIndex] = tempArr[i];
i++;
tempIndex++;
}
while(j<=right){
arr[tempIndex] = tempArr[j]; //右边还没有完，左边已完
j++;
tempIndex++;
}
}
测试算法，运行结果:
