排序算法归并排序

归并排序（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;
}

}```