归并排序的细节讲解与复杂度分析1.归并排序时间复杂度为O(N*logN)，额外的空间复杂度O(N)。
2.递归⾏为：⼀个数组的排序，先将左侧部分排好序，然后将右侧部分排好序，最后整体利⽤外排序的⽅式整体排好。
3.归并排序：将两个(或者两个以上)有序表合并成⼀个新的有序表，即把待排序的序列分成若⼲个⼦序列，在把有序的⼦序列合并为整体有序的序列。
算法思路：归并排序的中⼼思想是将两个已经排好的序列，合并成⼀个排序的序列4.递归排序举例 (1)对于数组：[5,3,6,2,0,1] 序列可以分为：[5,3,6]和[2,0,1] (2)对上⾯的序列分别进⾏排序，结果为： [3,5,6]和[0,1,2] 然后将上⾯的两个序列合并为⼀个排好序的序列 合并的⽅法是：设置两个指针，分别指着两个序列的开始位置，如下所⽰ [3,5,6] [0,1,2] /|\ /|\ (3)开始的时候两个指针分别指向3和0，这时我们找到⼀个空数组，将3和0中较⼩的值复制进这个数组中，并作为第⼀个元素。
新数组: [0,,,,,,] (4)后⾯数组的指针后移⼀位，如下所⽰ [3,5,6] [0,1,2] /|\ /|\ 将1和3进⾏⽐较，1⼩于3，于是将1插⼊新数组：[0,1,.......] (5)后⾯数组的指针后移⼀位，如下所⽰ [3,5,6] [0,1,2] /|\ /|\ 将2和3进⾏⽐较，2⼩于3，于是将2插⼊新数组：[0,1,2,.......] (6)将剩余的左边已经有序的数组直接复制进⼊新数组中去，可以得到新数组：[0,1,2,3,5,6] (7)有master公式(递归公式)：T(n)=2T(n/2)+O(N) 可以得出时间复杂度为：O(N*logN)5.java代码如下：import java.util.Arrays;public class MergeSort1 {public static void main(String[] args) {//先⽣成⼀个随机数组发⽣器int testTime = 500000;int maxSize =100;int maxValue=100;boolean succeed = true;for (int i = 0 ; i <testTime;i++){int[] arr1 = generateRandomArray(maxSize,maxValue);int[] arr2 = copyArray(arr1);mergeSort(arr1);comparator(arr2); //将数组arr2⽤⾃带的默认排序器进⾏排序if(!isEqual(arr1,arr2)){succeed=false;printArray(arr1);printArray(arr2);break;}}System.out.println(succeed?"Nice":"fucking fucked");int[] arr = generateRandomArray(maxSize,maxValue);printArray(arr);printArray(arr);}//testpublic static int[] generateRandomArray(int maxSize,int maxValue){int[] arr = new int[(int)((maxSize+1)*Math.random())]; //⽣成⼀个0到100维之间随机⼤⼩的数组for(int i =0 ; i<arr.length;i++){arr[i]=(int)((maxValue+1)*(Math.random()))-(int)((maxValue)*Math.random()); //⽣成两个0-100之间随机⼤⼩的整数，然后将两个整数相减 }return arr;}//testpublic static int[] copyArray(int[] arr){if(arr==null){return null;}int[] res = new int[arr.length];for(int i = 0 ;i <arr.length;i++){res[i]=arr[i];}return res;}//testpublic static void comparator(int[] arr){Arrays.sort(arr);}//testpublic static void printArray(int[] arr){if(arr==null){return;}for(int i = 0 ; i<arr.length;i++){System.out.print(arr[i]+"");}System.out.println();}//判断是否相等public static boolean isEqual(int[] arr1,int[] arr2){if((arr1==null&&arr2!=null)||(arr1!=null&&arr2==null)){return false;}if((arr1==null) && (arr2==null)){return true;}if(arr1.length!=arr2.length){return false;}for(int i =0 ; i <arr1.length;i++){if(arr1[i]!=arr2[i]){return false;}}return true;}public static void mergeSort(int[] arr){if(arr==null || arr.length<2 ){return;}mergeSort(arr,0,arr.length-1);}public static void mergeSort(int[] arr,int l, int r){if(l==r){return;}int mid = (l+r)/2;mergeSort(arr,l,mid);mergeSort(arr,mid+1,r);merge(arr,l,mid,r);}public static void merge(int[] arr, int l,int mid , int r) {int[] help= new int[r-l+1];int i =0 ;int p1= l ;int p2 = mid+1;while (p1<=mid&&p2<=r){help[i++] =arr[p1]<arr[p2]?arr[p1++]:arr[p2++];}while (p1<=mid){help[i++]=arr[p1++];}help[i++] = arr[p2++];}for(i = 0 ;i<help.length;i++){ arr[l+i]=help[i];}}}。
