package 排序;
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int[] arr1 = new int[]{22,3,56,6,46,61,1,6};
int[] temp = new int[arr1.length];
mergesort(0,arr1.length-1,arr1,temp);
System.out.println(Arrays.toString(arr1));
}
public static void mergesort(int low,int high,int[] arr,int[] temp){
if(low<high){
int mid = (low+high)/2;
mergesort(low,mid,arr,temp);
mergesort(mid+1,high,arr,temp);
merge(low,mid,high,arr,temp);
}
}
public static void merge(int low,int mid,int high,int[] arr,int[] temp){
int i=0;
int lo=low;
int ho=mid+1;
while(lo<=mid&&ho<=high){
if (arr[lo]<=arr[ho]){
temp[i++]=arr[lo++];
}else{
temp[i++]=arr[ho++];
}
}
while(lo<=mid){
temp[i++]=arr[lo++];
}
while(ho<high){
temp[i++]=arr[ho++];
}
for (int a=0;a<i;a++){
arr[low+a]=temp[a];
}
}
}
```java
for (int a=0;a<i;a++){
arr[low+a]=temp[a];
}
while(lo<=mid){
temp[i++]=arr[lo++];
}
while(ho<high){
temp[i++]=arr[ho++];
}
这两个while循环用来将还没有被合并的剩余元素依次加入到temp数组中。
for (int a=0;a<i;a++){
arr[low+a]=temp[a];
}
最后将temp数组中已经排序好的元素依次复制到原数组arr中。low+a 即为原始数组的实际位置,temp[a] 是从temp数组中取出来的元素值。