// copy tmpArray back
for (int i = 0; i < numElements; i++, rightEnd--)
arr[rightEnd] = tmpArray[rightEnd];//只拷贝当前 merge 的部分数组
/**
* 复制了整个数组中的所有元素
for(int i = 0; i < tmpArray.length; i++)
arr[i] = tmpArray[i];
*/
}
//for test purpose
public static void main(String[] args) {
Integer[] arr = {24,13,26,1,2,27,38,15};
mergeSort(arr);
for (Integer i : arr)
System.out.print(i + " ");
}
}
①第3行的公共方法，是对外的排序接口，首先创建一个临时数组tmpArray，用来保存合并过程中，两个子数组临时合并的结果。将tmpArray作为参数传递给递归调用的方法，而不是在执行递归调用的方法里面创建临时数组，这样可以大大地减少临时数组的创建。若在递归调用的方法里创建临时数组，每一层递归调用，都会创建一个临时数组。
②第15行的私有方法，是执行递归调用的方法。在某次具体的递归调用中，只用到了tmpArray中的某一部分空间(leftEnd 和 rightEnd之间的空间)。
③第38行while循环，比较两个子数组中的元素，谁小就把谁放到tmpArray中。
④第45行和第47行的两个while循环完成的功能是：当合并两个有序的子数组时，一个子数组中的元素已经全部放到tmpArray中去了，另一个子数组中还剩下有元素，故将剩下的所有元素直接复制到tmpArray中。
⑤第51行for循环，将本次merge完成的两个子数组复制到原数组中去。注意，它只复制本次参与合并的两个子数组中的元素。为什么要复制到原数组中去呢？因为在下一次的合并过程中，需要合并的是更大的子数组，这个更大的数组，就是由上次合并的生成的有序小数组组成的。比如：
在合并这两个数组时：[24] [13]
下一次合并的则是：[13,24] [1,26]
四，归并排序算法复杂度分析
归并排序中，用到了一个临时数组，故空间复杂度为O(N)
由归并排序的递归公式：T(N) = 2T(N/2) + O(N) 可知时间复杂度为O(NlogN)
数组的初始顺序会影响到排序过程中的比较次数，但是总的而言，对复杂度没有影响。平均情况 or 最坏情况下 它的复杂度都是O(NlogN)
此外，归并排序中的比较次数是所有排序中最少的。原因是，它一开始是不断地划分，比较只发生在合并各个有序的子数组时。
因此，Java的泛型排序类库中实现的就是归并排序。因为：对于JAVA而言，比较两个对象的操作代价是很大的，而移动两个对象，其实质移动的是引用，代价比较小。（排序本质上是两种操作：比较操作和移动操作）