Insertion Sort 与 Merge Sort的性能比较(Java)

    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] a = new int[n];
        
        //生成n个随机数(0至100)
        for(int i = 0; i < n; i++)
            a[i] = (int)(Math.random() * 100);
        
        /*long start = System.currentTimeMillis();
        InsertionSort(a);
        long end = System.currentTimeMillis();*/
        //100000个测试数据InsertionSort的排序时间约为2800ms
            
        /*System.out.println(Arrays.toString(a));
        System.out.println(start);
        System.out.println(end);
        System.out.printf("The time is: %d", end - start);*/
        
        //获取当前时间(ms)
        long start = System.currentTimeMillis();
        divide(a, 0, a.length - 1);
        long end = System.currentTimeMillis();
        //100000000个测试数据MergeSort的排序时间约为12000ms 10000000个测试数据用时约为1200ms
        //相对于平均时间复杂度O(n^2)的插入排序 随着测试数据数量级的增长 性能提升极大
        
        //System.out.println(Arrays.toString(a));
        System.out.println(start);
        System.out.println(end);
        System.out.println("The time is: " + (end - start));
    }
    
    /*public static void InsertionSort(int[] a)
    {
        for(int i = 1; i < a.length; i++)
        {
            int key = a[i];
            int j;
            for(j = i - 1; j >= 0 && key < a[j]; j--)
                a[j + 1] = a[j];
            a[j + 1] = key;
        }
    }*/
    
    public static void divide(int[] a, int front, int rear)
    {
        if(rear <= front)
            return;
        
        int mid = front + (rear - front) / 2;
        divide(a, mid + 1, rear);
        divide(a, front, mid);
        merge(a, front, mid, rear);
    }
    
    public static void merge(int[] a, int front, int mid, int rear)
    {
        int[] b = new int[rear - front + 1];
        int i = front, j = mid + 1, k = 0;
        
        while(i <= mid && j <= rear)
            if(a[i] < a[j])
                b[k++] = a[i++];
            else
                b[k++] = a[j++];
        
        if(i > mid)
            while(j <= rear)
                b[k++] = a[j++];
        else
            while(i <= mid)
                b[k++] = a[i++];
        
        for(int t = 0, q = front; t < b.length; t++, ++q)
            a[q] = b[t];
    }