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 ++];
}
}
}