算法练习(5) - 归并排序

package top.buukle.buukle._02MergeSort;

import org.junit.Test;

import java.util.Arrays;

public class MergeSort {

    @Test
    public void mergeSort_test() {
//        Integer[] A = {31,41,59,26,41,58};
        Integer[] A = {9,8,7,6,5,4,3,2,1};
        Integer leftIndex = 0 ;
        Integer rightIndex = A.length -1;
        int[] temp = new int[A.length];
        sort(A,leftIndex,rightIndex,temp);
        System.out.println(Arrays.asList(A));
    }

    private void sort(Integer[] a, Integer leftIndex, Integer rightIndex, int[] temp) {
	// 设置递归结束条件为 左右索引相逢时
	if(leftIndex < rightIndex){
		int middle = (leftIndex + rightIndex) / 2;
		sort(a,leftIndex,middle,temp);
		sort(a,middle + 1,rightIndex,temp);	
		merge(a,leftIndex,middle,rightIndex,temp);
	}

    }

    private void merge(Integer[] a, Integer leftIndex, Integer middle, Integer rightIndex, int[] temp) {
        int piLeft = leftIndex;
	int piRight = middle + 1;	
	int tIndex = 0;
    	// 将排序好的2个数组按顺序合并为1个数组,并写到temp临时数组中
	while(piLeft < middle + 1 && piRight < rightIndex + 1){
		if(a[piLeft] < a[piRight ] ){
			temp[tIndex++] = a[piLeft++];
		}else{
			temp[tIndex++] = a[piRight++];
		}
	}
	while(piLeft < middle + 1){
		temp[tIndex++] = a[piLeft++];
	}
	while(piRight < rightIndex + 1){
		temp[tIndex++] = a[piRight++];
	}
	// 将临时数组的值,拷贝到原数组相应的索引之中
	tIndex =0;
	int copyIndex = leftIndex;
	while(leftIndex < rightIndex + 1){
		a[copyIndex ++] = temp[tIndex ++];
	}
    }

}