- 算法思想
归并排序中使用分治法。将原来的问题划分成子问题，然后递归求解子问题，然后再合并这些子问题的解。 - 时间复杂度
归并排序无论什么情况都是O(nlgn)
可以理解为每个要归并排序的数组大致会被分成lgn层。每一层都有n个元素
例如归并排序数组
int[] num = {32,2,1,6,23,11,10,43,2};
最开始通过数组下标low=0和长度high=8找到中间值mid=(low+high)/2。此时把原问题分解成2个子问题，然后再对两个子问题进行归并排序。先把0-mid子数组排序，然后mid+1-high排序
public static int[] mergeSort(int[] num,int low,int high) {
int mid = (low+high)/2;
if (low<high) {
mergeSort(num, low, mid);
mergeSort(num, mid+1, high);
mergeSort( num, low, mid,high);
}
return num;
}
private static void mergeSort(int[] num, int low, int mid, int high) {
int[] temp = new int[high-low+1];
int i=low;
int j=mid+1;
int k=0;
while(i<=mid&&j<=high){
if (num[i]<num[j]) {
temp[k++]=num[i++];
}else {
temp[k++]=num[j++];
}
}
while(i<=mid){
temp[k++]=num[i++];
}
while(j<=high){
temp[k++]=num[j++];
}
for (int k2 = 0; k2 < temp.length; k2++) {
num[k2+low]=temp[k2];
}
}
