归并排序的思想：

先实现一个数组的中间位置“断裂”为两个子数组，利用索引实现，一直到每一个都被分开；
直到最后两个数据都被分开后，然后借助辅助数组实现排序与合并操作；
最后递归返回到最初的时候，便实现了整个递归排序

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

归并排序

归并排序的代码实现：

public class MergeSort{
  // 单独列出此函数，而不是直接调用Sort是因为输入只有arr数组，同时为了更好递归而设置的
  public static void MergeSort(int[] arr){
    Divide(arr, 0, arr.length-1)  
  }

  private static void Divide(int[] arr, int left, int right){
    if(left >= right) return;
    int mid = (left + right)/2;
    // 左右部分依次断裂，减少交换数据的作用
    Divide(arr, right, mid);
    Divide(arr, mid+1, right);
    // 最后才比较大小归并数组
    MergeAndSort(arr, left, mid, right);
  }

  private static void MergeAndSort(int[] arr, int left, int mid, int right){
    int[] tmpArr = new int[a.lenght];
    int rightStartIndex = mid + 1;
    int tmpIndex = left;
    int copyIndex = left;

    // 比较左右两部分数组的大小，小的放入到tmpArr数组中
    while(left <= mid && rightStartIndex <= right){
      if(arr[left] < arr[rightStartIndex]) tmpArr[tmpIndex++] = arr[left++];
      else tmpArr[tmpIndex++] = arr[rightStartIndex++];
    }
    // 判断左边是否还有数据剩余，如果有则把数据拷贝到tmpArr数组右边，因为左边已经是排好序的，所以剩余的数据肯定是最大的
    while(left <= mid){
      tmpArr[tmpIndex++] = arr[left++];
    }
    // 判断右边是否还有数据剩余，如果有则把数据拷贝到tmpArr数组右边，因为右边已经是排好序的，所以剩余的数据肯定是最大的
    while(rightStartIndex <= right){
      tmpArr[tmpIndex++] = arr[rightStartIndex++];
    }
    // 把tmpArr数组排好序的数据依次拷贝到原数组中
    while(copyIndex <= right){
      arr[copyIndex] = tmpArr[copyIndex];
      copyIndex++;
    }
  }
}

时空复杂度

时间复杂度

分析：主要是考虑两个函数的时间花销，一、数组划分函数Divide()；二、有序数组归并函数MergeAndSort()；
①调用Divide()函数把原数组划分成两部分，那每一小部分排序好所花时间则为 T[n/2]。
②MergeAndSort()函数的时间复杂度为O(n)，有两个时间复杂度为O(n)的while，一个是把非排序的数据保存到辅助数组，一个是把辅助数组中的数据拷贝到原数组。所以，2O(n) = O(n)
③把两部分都合并起来，就是
T(n) = 2T(n) + O(n)

结果就是T(n) = O(n*lgn)