归并排序（Merging Sort）利用归并的思想实现的排序方法。它的原理是假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列长度为1，然后两两归并，得到[n/2]个长度为2或1的有序子序列然后反复进行两两归并，直到得到一个长度为n的有序序列为止。
时间复杂度
最好情况o(nlogn)
最坏情况o(nlogn)
排序稳定，但需要额外的辅助空间
1.递归实现
static void partSort(int[] array, int left, int right) {
if (array != null && array.length > 0) {
if (left >= right)
return;
// 找出中间索引
int center = (left + right) / 2;
// 对左边数组进行递归
partSort(array, left, center);
// 对右边数组进行递归
partSort(array, center + 1, right);
//合并
megre(array, left, center, right);
}
}```
/**
- 将左右两边有序的数据进行合并
*/
static void megre(int[] array, int left, int center, int right) {
if (array != null && array.length > 0) {
// 临时数组
int[] tmpArray = new int[array.length];
// 右数组第一个元素索引
int mid = center + 1;
// tag 记录临时数组的索引
int tag = left;
// 缓存左数组第一个元素的索引
int tmp = left;
while (left <= center && mid <= right) {
// 从两个数组中取出最小的放入临时数组
if (array[left] <= array[mid]) {
tmpArray[tag++] = array[left++];
} else {
tmpArray[tag++] = array[mid++];
}
}
// 剩余部分依次放入临时数组（实际上两个while只会执行其中一个）
while (mid <= right) {
tmpArray[tag++] = array[mid++];
}
while (left <= center) {
tmpArray[tag++] = array[left++];
}
// 将临时数组中的内容拷贝回原数组中
// （原left-right范围的内容被复制回原数组）
while (tmp <= right) {
array[tmp] = tmpArray[tmp++];
}
}
}
**2.非递归实现**
非递归思想: 将数组中的相邻元素两两配对。用merge函数将他们排序，构成n/2组长度为2的排序好的子数组段，然后再将他们排序成长度为4的子数组段，如此继续下去，直至整个数组排好序。性能由于递归实现
static void megeringSort(int[] array) {
int len = 1;
//程序边界的处理非常重要
while (len <= array.length) {
for (int i = 0; i + len <= array.length - 1; i += len * 2) {//len 1 2 4 8... ...
int low = i, mid = i + len - 1, high = i + len * 2 - 1; //计算每次区间的左中右索引
if (high > array.length - 1) high = array.length - 1;
megre(array, i, mid, high);//执行合并
}
len *= 2;
}
}```
