一趟归并需要将数组 a[]中相邻的长度为h的有序序列进行两两归并.并将结果放到temp[]中，这需要将待排序列中的所有记录扫描一遍，因此耗费O(n)，而又完全二叉树的深度可知，整个归并排序需要进行（）次，因此总的时间复杂度为O(nlogn)，而且这是归并排序算法中最好、最坏、平均的时间性能。
由于归并排序在归并过程中需要与原始序列同样数量的存储空间存放归并结果以及递归时深度为的栈空间，因此空间复杂度为O(n+logn).
另外，对代码进行仔细研究，发现merge函数中有if (a[i] < a[j]) 的语句，说明它需要两两比较，不存在跳跃，因此归并排序是一种稳定的排序算法。
也就是说，归并排序是一种比较占内存，但却效率高且稳定的算法。
（1）申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
（2）设定两个指针，最初位置分别为两个已经排序序列的起始位置
（3）比较两个指针所指向的元素，选择相对小的元素放入到合并空��，并移动指针到下一位置
（4）重复步骤3直到某一指针达到序列尾
（5）将另一序列剩下的所有元素直接复制到合并序列尾
package MySort;
import java.util.Arrays;
public class MySortTest8 {
public static void main(String[] args) {
int[] data = { 1, 3, 6, 2, 4, 8, 9, 5, 12 };
// 4.归并排序
mergeSort(data, 0, data.length - 1);
System.out.println("归并排序：\t" + Arrays.toString(data));
}
private static void mergeSort(int[] data, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
// 左边
mergeSort(data, low, mid);
// 右边
mergeSort(data, mid + 1, high);
// 左右归并
merge(data, low, mid, high);
}
}
public static void merge(int[] data, 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 (data[i] < data[j]) {
temp[k++] = data[i++];
} else {
temp[k++] = data[j++];
}
}
// 把左边剩余的数移入数组
while (i <= mid) {
temp[k++] = data[i++];
}
// 把右边边剩余的数移入数组
while (j <= high) {
temp[k++] = data[j++];
}
// 把新数组中的数覆盖nums数组
for (int k2 = 0; k2 < temp.length; k2++) {
data[k2 + low] = temp[k2];
}
}
}
8.基数排序 8.1.基本思想像选择排序、插入排序、快速排序等都是基于两个元素的比较进行排序的。而基数排序无需进行元素比较，基于队列处理就能够达到排序的目的。
基数排序不是基于排序关键字来比较排序项，而是基于排序关键字的结构。对于排序关键字中的每一个数字或字符的每一种可能取值，都会创建一个单独的队列。队列的数目就称为基数。
例如：要排序全部由小写字母组成的字符串，则基数就是26，就会用到26个单独的队列。如果对十进制数进行排序，则基数应该是10.
8.2.复杂度分析