思路：

将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列

单趟逻辑：

Void merge (int []a , int left, int right, int middle)
{
       //开辟新的空间，记录合并后的数据
       int [] tempArr = new int [a.length];
       int mid = middle + 1; //右侧开始位置
       int cur = left ; //记录新数组插入位置
       int temp = left; //用于将新数组赋值回原数组
       while(left <= middle && mid <= right)
       {
              //从两个数组里选小的数放到新数组中
              if (a[left] <= a[mid])
                      tempArr[cur ++] = a[left ++];
              else
                      tempArr[cur ++] = a[mid++];
              //将两个数组剩余的数插入新数组
              while(left <= middle)
                      tempArr[cur++] = a[left++]

while(mid < =right)
                tempArr[cur++] = a[mid ++];
     while(temp < =right)
     {
            a[temp] = tempArr[temp];    temp++;
     }
  }
}
void mergeSort(int  []a, int left, int right)
{
         if(left < right)
         {
               int middle = (left +right)/2;
               mergeSort (a, left, middle);//对左边进行递归
               mergeSort(a, middle+1,right);//右边 
               merge(a, left, right, middle); //合并
         }