归并排序

归并排序算法会把序列分成长度相同的两个子序列，当无法继续往下分时（也就是每个子序列中只有一个数据时），就对子序列进行归并。归并指的是把两个排好序的子序列合并成一个有序序列。该操作会一直重复执行，直到所有子序列都归并为一个整体为止。

归并排序中，分割序列所花费的时间不算在运行时间内（可以当作序列本来就是分割好的）。在合并两个已排好序的子序列时，只需重复比较首位数据的大小，然后移动较小的数据，因此只需花费和两个子序列的长度相应的运行时间。也就是说，完成一行归并所需的运行时间取决于这一行的数据量。看一下上面的图便能得知，无论哪一行都是 n 个数据，所以每行的运行时间都为 O(n)。而将长度为 n 的序列对半分割直到只有一个数据为止时，可以分成 log2n 行，因此，总共有 log2n 行。也就是说，总的运行时间为 O(nlogn)

实现 MergeSort

import java.util.Arrays;


public class MergeSort {

    private MergeSort(){}

    public static <E extends Comparable<E>> void sort(E[] arr){

        sort(arr, 0, arr.length - 1);
    }

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

        if (l >= r) return;

        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 ++){
            //  i > mid 说明 i 越界了,  这个时候的值就只能取右边的了 
            if(i > mid){
            	//  temp和arr 有 l  偏移量, 右侧值自增一次
                arr[k] = temp[j - l]; j ++;
            }
             //  (j > r) 说明 j 越界了,  这个时候的值就只能取左边的了边的了
            else if(j > r){
                arr[k] = temp[i - l]; i ++;
            }
            else if(temp[i - l].compareTo(temp[j - l]) <= 0){
                // 左边的更小  , 取左边
                arr[k] = temp[i - l]; i ++;
            }
            else{
                arr[k] = temp[j - l]; j ++;
            }
        }
    }

    public static void main(String[] args){
        Integer[] arr =  {6, 4, 3, 7, 5, 1, 2};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

C