算法学习：归并排序

**背景介绍： **
是创建在归并操作上的一种有效的排序算法，效率为O(n log n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。 ----- 来自 wikipedia

算法规则：
像快速排序一样，由于归并排序也是分治算法，因此可使用分治思想：
1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2.设定两个指针，最初位置分别为两个已经排序序列的起始位置
3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4.重复步骤3直到某一指针到达序列尾
5.将另一序列剩下的所有元素直接复制到合并序列尾

代码实现（Java版本）

  public static int[] mergeSort(int[] nums, int low, int high) {  
      int mid = (low + high) / 2;  
      if (low < high) {  
          // 左边  
          mergeSort(nums, low, mid);  
          // 右边  
          mergeSort(nums, mid + 1, high);  
          // 左右归并  
          merge(nums, low, mid, high);  
      }  
      return nums;  
  }  

  public static void merge(int[] nums, 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 (nums[i] < nums[j]) {  
              temp[k++] = nums[i++];  
          } else {  
              temp[k++] = nums[j++];  
          }  
      }  

      // 把左边剩余的数移入数组  
      while (i <= mid) {  
          temp[k++] = nums[i++];  
      }  

      // 把右边边剩余的数移入数组  
      while (j <= high) {  
          temp[k++] = nums[j++];  
      }  

      // 把新数组中的数覆盖nums数组  
      for (int k2 = 0; k2 < temp.length; k2++) {  
          nums[k2 + low] = temp[k2];  
      }  
  }