import java.lang.reflect.Array;
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 ) / 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); //前闭后开，所以要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 ++;
            }
            else if(temp[i - l].compareTo(temp[j - l]) <= 0){
                arr[k] = temp[i - l]; i ++;
            }
            else{
                arr[k] = temp[j - l]; j ++;
            }
            // arr[i] 和 arr[j]

        }
    }

    public static void main(String[] args){

        int n = 100000;
        Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
        MergeSort.sort(arr);
        for(int i = 0 ; i < n ; i++){
            System.out.println(arr[i]);
        }
    }
}

import java.util.Random;

public class ArrayGenerator {

    private ArrayGenerator(){}

    public static Integer[] generateOrderedArray(int n){

       Integer[] arr = new Integer[n];
       for(int i = 0; i < n ; i++)
           arr[i] = i;
       return arr;
    }

    // 生成一个长度为 n 的随机数组， 每个数字的范围是[ 0 , bound)
    public static Integer[] generateRandomArray(int n, int bound){

        Integer[] arr = new Integer[n];
        Random rnd = new Random();
        for(int i = 0 ; i < n; i++)
            arr[i] = rnd.nextInt(bound); //从0到bound前闭后开
        return arr;
    }
}