[数据结构与算法]java实现归并排序

原文链接：https://www.cnblogs.com/of-fanruice/p/7678801.html
理解后代码尝试如下

public class test1024 {
    public static void main(String []args){
        int []arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int[] array) {
    	int[] copy = new int[array.length];
    	mergesort(array, 0, array.length - 1, copy);
    }
    public static void mergesort(int[] array, int left, int right, int[] copy) {
    	if(left >= right) return;
    	int mid = (left + right) / 2;
    	mergesort(array, left, mid, copy);
    	mergesort(array, mid + 1, right, copy);
    	merge(array, left, mid, right, copy);
    }
    public static void merge(int[] array, int left, int mid, int right, int[] copy) {
    	int i = left, j = mid + 1, index = left;
    	while(i <= mid && j <= right) {
    		if(array[i] < array[j]) copy[index++] = array[i++];
    		else copy[index++] = array[j++];
    	}
    	while(i <= mid) copy[index++] = array[i++];
    	while(j <= right) copy[index++] = array[j++];
    	for(int m = left; m <= right; m ++) {
    		array[m] = copy[m];
    	}
    }
}

归并排序特点

（1）稳定排序
　归并排序是一种稳定的排序。
（2）存储结构要求
　可用顺序存储结构。也易于在链表上实现。
（3）时间复杂度
　对长度为n的文件，需进行趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。
（4）空间复杂度
　 需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。
注意：
　若用单链表做存储结构，很容易给出就地的归并排序