归并排序分为两部分：分解，合并。
分解:归并算法会把数组分成两个长度相同的子数组，直到无法再分割,每个数组只有一个元素。此过程不消耗时间资源。对应的时间复杂度为O(1)。
合并:首先比较两个数组内的各个元素大小，然后根据比较结果将两个数组合并成一个有序数组。此过程会将每行的所有的子数组内的所有元素进行一次比较合并，所以完成一行的归并操作所对应的时间复杂度为O(N)。
分解元素时采用的是二分法对半分割，所以数组被分解为log2N次，即8个元素的数组会被分解三次。所以合并时，也总计需要log2N次的时间合并。
因为共有N个元素，且分解log2N次。 所以两者总计时间为O(N*log2N)。将log2N次的数据合并完成后，排序结束。
文章中使用的动画网站地址，限 pc: 排序算法动画
http://www.donghuasuanfa.com/sort
算法一览表：https://blog.csdn.net/ww753951/article/details/106862328
来自百度百科
public class MergeSort {
public static int[] mergeSort(int[] nums, int l, int h) {
if (l == h)
return new int[] { nums[l] };
int mid = l + (h - l) / 2;
int[] leftArr = mergeSort(nums, l, mid); //左有序数组
int[] rightArr = mergeSort(nums, mid + 1, h); //右有序数组
int[] newNum = new int[leftArr.length + rightArr.length]; //新有序数组
int m = 0, i = 0, j = 0;
while (i < leftArr.length && j < rightArr.length) {
newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
}
while (i < leftArr.length)
newNum[m++] = leftArr[i++];
while (j < rightArr.length)
newNum[m++] = rightArr[j++];
return newNum;
}
public static void main(String[] args) {
int[] nums = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 10 };
int[] newNums = mergeSort(nums, 0, nums.length - 1);
for (int x : newNums) {
System.out.println(x);
}
}
}
首先进行第一部分分解处理,将数量为N的数组分解为只有一个元素的数组。
1.首先将45和6置成灰色进行比较，因为45大于6，所以合并时将6和45互换位置。
2.比较23和12的位置，因为23大于12。所以合并时互换位置。
3.此时合并后分为两个数组[6,45]和[12,23]。再将 [6,45]和[12,23]进行合并。每个数组从左到右比较数组内元素的值，将比较后较小的元素放到对应的位置。最终数组整体排序完成。
| 最差时间复杂度 | 平均时间复杂度 | 最优时间复杂度 |
|---|---|---|
| O ( N ∗ l o g 2 N ) O(N*log_{2}N) O(N∗log2N) | N ∗ l o g 2 N N*log_{2}N N∗log2N | N ∗ l o g 2 N N*log_{2}N N∗log2N |
上半部分，分的过程。归并排序的时间复杂度恒定为 N*log2N。将数组分解为单个元素分解的时间为O(1)。即默认可认为元素已分解为单个元素。
下半部分，治的过程。每一层的各个元素都要进行比较，每层各个元素比较的过程的时间复杂度为N。共需要进行 log2N 次的合并(例如:8位数组的合并次数为 log28=3，4位的为log24=2)。所以总计的时间复杂度为 N *log2N 。
插入排序需要的空间复杂度为 O(N)。即：每一层的处理都需要额外的与数组相同的空间存储新一层的数据。理论上合并的总的空间复杂度为 N *log2N (分的过程由于可直接认为数组为已分割的单个元素数组，所以分的时间复杂度忽略不计)。
每次元素合并后，占用的空间可释放，所以时间空间复杂度不是 N *log2N。而是 O(N)。
两个元素的值相同时如果最终排序完成后位置不变，则为稳定排序，如果位置变更则为不稳定排序。
排序算法中，如果数字相同，则无需变更位置，避免额外的操作。归并排序，比较判断时，无需更换位置也能达到排序效果，所以为稳定排序。