Merge Sort

public class MergeSort {

    private MergeSort(){}

    public static <E extends Comparable<E>> void sort(E[] arr){
        sort(arr, 0, arr.length - 1);   // 传入 0， 最后个位置
    }

    private static <E extends Comparable<E>> void sort(E[] arr, int l, int r){

        if (l >= r) return; // 终止条件是 l=r 表示只有一个元素

        int mid = l + (r - l) / 2;  // 获取索引的中间值
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    // 合并两个有序的区间 arr[l, mid] 和 arr[mid + 1, r]
    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r){

        // 这里有一个额外的拷贝动作，因此需要更多的内存空间，相对于其他排序算法
        E[] temp = Arrays.copyOfRange(arr, l, r + 1);

        int i = l, j = mid + 1;

        // 每轮循环为 arr[k] 赋值
        for(int k = l; k <= r; k ++){

            if(i > mid){    // 表示左侧没值了。
                arr[k] = temp[j - l]; j ++;
            }
            else if(j > r){ // 表示 右侧没有值了。
                arr[k] = temp[i - l]; i ++; // i++前进
            }
            else if(temp[i - l].compareTo(temp[j - l]) <= 0){   // arr数组值已经变了，需要从temp去比较
                arr[k] = temp[i - l]; i ++;
            }
            else{
                arr[k] = temp[j - l]; j ++;
            }
        }
    }
}