Java版归并排序[稳定]

原理：采用分治法

复杂度：O(nlogn) - O(nlgn) - O(nlgn) - O(n)[平均 - 最好 - 最坏 - 空间复杂度]

// 排序public void mergeSort(int[] a, int low, int high) {int mid = (low + high) / 2;if (low < high) {// 左边排序mergeSort(a, low, mid);// 右边排序mergeSort(a, mid + 1, high);// 有序序列合并merge(a, low, mid, high);}}// 合并private void merge(int a[], int low, int mid, int high) {// 临时数组int[] temp = new int[high - low + 1];// 左指针int i = low;// 右指针int j = mid + 1;// 临时数组索引int k = 0;while (i <= mid && j <= high) {if (a[i] < a[j]) {temp[k++] = a[i++];} else {temp[k++] = a[j++];}}// 把左边剩余的数移入数组  while (i <= mid) {temp[k++] = a[i++];}// 把右边剩余的数移入数组  while (j <= high) {temp[k++] = a[j++];}// 注意这里是low + tfor (int t = 0; t < temp.length; t++) {a[low + t] = temp[t];}}