//归并排序
public class d1 {
//归并1-->递归形式
public static void guibing1(int[]arr,int L,int R){
if (L == R) { // base case
return;
}
int mid = L + ((R - L) >> 1);
guibing1(arr, L, mid);
guibing1(arr, mid + 1, R);
merge(arr, L, mid,R);
}
public static void merge(int[]arr,int l,int m,int r){
int[]help=new int[r-l+1];
int i=0;
int p1=l;
int p2=m+1;
while(p1<=m&&p2<=r){
help[i++]=arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];
}
while(p1<=m){
help[i++]=arr[p1++];
}
while(p2<=r){
help[i++]=arr[p2++];
}
for(i=0;i<help.length;i++){
arr[l+i]=help[i];
}
}
public static void parr(int[]arr){
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}
//归并2->非递归形式
public static void guibing2(int[]arr){
int n=arr.length;
int mergesize=1;//每组的大小
while(mergesize<n){
int l=0;//左组开始下标
while(l<n){
int m=l+mergesize-1;//左组结束下标
if(m>=n) break;
int r=Math.min(m+mergesize,n-1);//右组结束下标
merge(arr,l, m,r);
l=r+1;
}
if(mergesize>n/2) break;
mergesize<<=1;
}
}
public static void main(String[] args) {
int[]a={7,6,5,4,3,2,1,2,11,99,88,77,66,55,44,33,22,11};
guibing2(a);
parr(a);
}
}