排序方法将一系列数分成两半进行排序，然后将这一半合并以分析时间的复杂性。
最佳： o(nlogn )、顺序最差： o(nlogn )、逆序空间复杂性：
o(n )稳定排序
不当场排序
代码publicstaticvoidmergesort (int [ ] arr ) if ) arr.length==0) return； int[] result=new int[arr.length]； 合并软件(arr，0，arr.length - 1，result )； (//arr的[start，end]区间合并排序专用语音合成器(int [ ] arr，int start，int end，int[] result ) ) /是一个数字//分割左边的区域，将合并排序的结果在result的[start，middle]区间mergesort(arr，start，middle，result )； //分割右侧区域，将合并排序的结果在result的[middle 1，end]区间mergesort(arr，middle 1，end，result )； //将左右区域合并为result的[start，end]区间merge(arr，start，end，result )； (在result的[start，middle]和[middle 1，end]区间为私有状态语音卷(int ) ) arr、int start、int end、int ) ) resull int end1=middle； //序列2的首尾位置int start2=middle 1； int end2=end； //用于遍历数组的指针int index1=start1； int index2=开始2； //结果数组的指针int resultIndex=start1； while(index1=end1index2=end2) if ) arr[index1]=arr[index2] ) result [ result index ]=arr [ index1]； } else { result [ result index ]=arr [ index2]； }//将剩下的数字添加到结果数组后while(index1=end1) result [ result index ]=arr [ index1]； }while(index2=end2) result [ result index ]=arr [ index2]； //下次for (为了比较inti=start，将result操作区间的数字复制到arr数组中的i=end； I({arr[I]=result[I]； }} 原地归并
分析下面的代码可以看到，这样实现的合并本质上是插入排序！
下面的代码用于在合并arr的“开始，中间”和“中间1，结束”区间时，将两个区间中的较小数字移动到索引1的位置，并不断向后移动左侧区域，以留出新插入的数字的位置最后更新两个区间的下标，继续合并更新后的区间。 publicstaticvoidmergesort (int [ ] arr ) if ) arr.length==0) return； 合并软件(arr，0，arr.length - 1 )； //arr的[start，end]区间合并排序专用语音识别器sort (int [ ] arr，int start，int end ) )//只剩下一个数字，而分区if (starrart if ) //分割左区域的合并软件(arr、start、middle )； //分割右侧区域mergesort(arr，middle 1，end )； //合并左右区域合并(arr，start，end )； (//arr的[start，middle]和[middle 1，end]之间的区间为私有staticvoidmerge (int [ ] arr，int start，int end ) ) int end () //用于遍历数组的指针int index1=start； int index2=开始2； while({ index1=end1index2=end ) if ) arr[index1]=arr[index2] ) index1； (else(/右边区域的这个数字小于左边区域的数字，所以站起来int value=arr[index2]； int index=index2； //前面的数字不断地是while(indexindex1) { arr[index]=arr[index - 1]； 索引- -； (//这个数字坐在索引1的位置arr [索引]=value； //更新所有下标，进入1格索引1； 索引2； 结束1； }}下面的代码在合并区间时，同样将两个区间中的小数字移动到索引1的位置，但采用的是直接交换两个区间中的第一个数字的想法。 更换完成后，将右侧区间更换的数字不断向后移动，使右侧区间保持有序。 publicstaticvoidmergesort (int [ ] arr ) if ) arr.length==0) return； 合并软件(arr，0，arr.length - 1 )； //arr的[start，end]区间合并排序专用语音识别器sort (int [ ] arr，int start，int end ) )//只剩下一个数字，而分区if (starrart if ) //分割左区域的合并软件(arr、start、middle )； //分割右侧区域mergesort(arr，middle 1，end )； //合并左右区域合并(arr，start，end )； (//arr的[start，middle]和[middle 1，end]之间的区间为私有staticvoidmerge (int [ ] arr，int start，int end ) ) int end () //用于遍历数组的指针int index1=start； 将while(index1=end1start2=end ) if(arr[index1]arr[start2] )//index1和start2的下标数字改为exchange(arr，index1，start2)=end (调整由/start 2替换的此数字的位置，右侧区域有序int value=arr[start2]； int index=开始2； //右侧区域小于arr[start2]的数字为while [ indexendarr [ index1] value ] { arr [ index ]=arr [ index1]； 索引； () /在右区域交换的这个数字找到了自己合适的位置，坐下来arr[index]=value； } }索引1； }隐私声明(int [ ] arr，int i，int j ) { int temp=arr[i]； arr[i]=arr[j]； arr[j]=temp； }