归并排序算法的效率是很快的，只是比快速排序稍逊一筹
归并排序的原理实际上是通过不断的分割待排序的数据，直至不能分割，就认为这个时候不能再分割的最小数组单元，就是已经排好顺序的数据。然后合并排序相邻的数组。
例子：现在有一个待排序的数组a:{10,19,4,33,2,32,25}
第一次分割后为：a1:{10,19,4} 、 a2:{33,2,32,25}
第二次分割后为： a11:{10} 和 a12:{19,4}、a21:{33,2} 和 a22:{32,25}
第三次分割后为：a11:{10}(不能再分割)、a121:{19} 和 a122:{4}、a211:{33} 和 a212:{2}、a221:{32}和a222:{25}
现在数据都不能再分割了，我们认为此时的每一个最小单元的数据都是已经排好顺序的数据，然后把相邻的数据逐步合并排序在一起。
第一次合并：b1:{10}、b2:{4,19}、b3:{2,33}、b4:{25,32}
第二次合并：b12:{4,10,19}、b34:{2,25,32,33}
第三次合并：b14:{2,4,10,19,25,32,33}
代码实现为：
package sort;
public class MergeSort {
public static void main(String[] args) {
double[] array = {12.0, 32.0, 3.0, 2.0, 54.0, 23.0, 43.0, 76.0, 44.0, 54.0, 43.0, 13.0};
double[] temp = new double[20];
//调用归并排序算法
mergeSort(array, 0, array.length-1, temp);
print(array, array.length);
}
private static void print(double[] array ,int size) {
for(int i=1; i<size; i++){
System.out.print(array[i] + " ");
}
}
private static void mergeArray(double[] array, int start, int middle, int end, double[] temp) {
int i = start, j = middle+1;
int k = 0;
//把较小的数据拷贝到temp数组里
while (i <= middle && j <= end) {
if(array[i] < array[j]){
temp[k++] = array[i++];
}else {
temp[k++] = array[j++];
}
}
//如果数据的前半部分没有拷贝完
while (i <= middle) {
temp[k++] = array[i++];
}
//如果数据的后半部分没有拷贝完
while (j <= end) {
temp[k++] = array[j++];
}
//把排序后的数据，整体拷贝到array数组里
for(i=0; i< k; i++){
array[start+i] = temp[i];
}
}
private static void mergeSort(double[] array, int start, int end, double[] temp) {
if(start < end){
int middle = (start + end)/2;//把数据分割为两部分
mergeSort(array, start, middle, temp);//数组的前一半，继续分割
mergeSort(array, middle+1, end, temp);//数组的后一半，继续分割
mergeArray(array, start, middle, end, temp);//合并分割后的数据单元
}
}
}