归并排序是一种十分优秀的排序方法，在一开始学习的时候可能会对它的实现思路有点难以理解，不过当你想通了之后就会发现这种方法的绝妙之处。

由上图应该可以很清楚的理解到归并排序的基本步骤就是
1.先把一个数组以二分法的方式递归的分组，（分）
2.然后再将相邻的两个数组进行作对比，把两个已排序好的子数组中的数字由小到大（由大到小）地放到辅助数组temp[]中，（合）
3.最后再把辅助数组中的元素复制到原数组中返回。

这种排序的@R_433_1304@为O(NlgN),同时需要O(N)的辅助空间——保存N个元素。
这是一种稳定的算法。

代码实现如下：

    public static void mergeSort(int[] nums) {         //创建与原数组相同长度的数组         int[] temp = new int[nums.length];         mergeSort(nums, temp, 0, nums.length-1);     }      private static void mergeSort(int[] nums, int[] temp, int left, int right) {          if(left < right) {             //从中间将数组分成两半             int mid = (left + right) >> 1;             mergeSort(nums, temp, left, mid);             mergeSort(nums, temp, mid+1, right);             //将两个数组重新合并             merge(nums, temp, left, mid+1, right);         }     }      private static void merge(int[] nums, int[] temp,              int leftPos, int rightPos, int rightEnd) {                  int leftEnd = rightPos - 1;         int tmpPos = leftPos;         int numElements = rightEnd - leftPos + 1;         //对比左右两个数组并将较小的数先放到辅助数组         while(leftPos <= leftEnd &amp;& rightPos <= rightEnd) {             if(nums[leftPos] <= nums[rightPos]) {                 temp[tmpPos++] = nums[leftPos++];             }else {                 temp[tmpPos++] = nums[rightPos++];             }         }         //把左边数组剩下的原数放到辅助数组         while(leftPos <= leftEnd) {             temp[tmpPos++] = nums[leftPos++];         }         //把右边数组剩下的原数放到辅助数组         while(rightPos <= rightEnd) {             temp[tmpPos++] = nums[rightPos++];         }         //把辅助数组复制到原数组         for(int i = 0; i < numElements; i++,rightEnd--) {             nums[rightEnd] = temp[rightEnd];         }     }