归并排序

归并排序的基本思路是计算当前区间的下标中点，以中点将区间划分为左右两个相等大小的区间，递归对左右区间调用归并排序，直到区间left == right，即区间只有一个元素时，调用归并函数，函数调用开始向上返回。

归并排序的结构类似于二叉树的后续遍历，先处理左右子区间，处理妥善了之后交给父节点整理结果。也就是说归并排序是一个自底向上的思路。

具体实现上，完整的归并排序包含一个递归的mergeSort方法和一个后序调用的整合子节点排序结果的方法merge。

merge方法的原理是，对于已经排好序的左右两个子区间，每次比较两个区间的头元素，将较小的那一个复制到原数组的恰当位置上，更新原数组下标和当前子区间下标，当两个子区间有一个取完了之后，将剩下的那一个区间的剩余元素复制到原数组中。

由于归并排序的操作是覆盖而非快排的交换，所以需要临时数组保存当前轮次左右区间的元素信息。

public class MergeSort {
    private int[] tempArr1;
    private int[] tempArr2;

    private void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    private void merge(int[] arr, int left, int mid, int right) {
        int len1 = mid - left + 1;
        int len2 = right - mid;

        System.arraycopy(arr, left, tempArr1, 0, len1);
        System.arraycopy(arr, mid + 1, tempArr2, 0, len2);

        // 记录当前轮次左右子区间下一个待访问位置
        int i = 0;
        int j = 0;
        // 记录当前轮次原数组中待覆盖的下一个位置
        int k = left;
        while (i < len1 && j < len2) {
            if (tempArr1[i] > tempArr2[j]) {
                arr[k] = tempArr1[i];
                i++;
            } else {
                arr[k] = tempArr2[j];
                j++;
            }
            k++;
        }
        // 哪一个子区间有剩余，就将剩余元素覆盖到原数组上
        while (i < len1) {
            arr[k] = tempArr1[i];
            i++;
            k++;
        }

        while (j < len2) {
            arr[k] = tempArr2[j];
            j++;
            k++;
        }
    }
}