import java.util.*;

/*歸并排序
 *將數組中的各個數兩兩合并（兩個數），直到合并的長度為（n/2）（這些小的數也是有序的），
 *然后成一個有序的數組；
 **/
public class MergeSort{
	public static void main(String args[]){
		int n=20;
		int k=1; 
		// 獲得數據源
		Random rand=new Random();
		int arraynum[]=new int[n];
		int swap[]=new int[n];
		System.out.println("DataSource:");
		for(int i=0;i<n;i++){
			arraynum[i]=Math.abs(rand.nextInt()%100);
			System.out.print(arraynum[i]+"  ");
		}
		System.out.println("");
		
		
		//調用歸并排序方法
		while(k<n){
			M_S(arraynum,n,swap,k);
			for(int i=0;i<n;i++){
				arraynum[i]=swap[i];
			}
			k=2*k;
		}
		
		System.out.println("Merge_SortData:");
		for(int i=0;i<n;i++){
			System.out.print(arraynum[i]+"  ");
		}
		System.out.println("");
		
	}
	
	//歸并排序方法。
	static void M_S(int a[],int n,int swap[],int k){
		int l1,l2,u1,u2,i,j,m=0;
		l1=0;
	
		//確定兩個要合并的小數組的上下界,把他們合并成一個小數組再排序
		while(l1+k<=n-1){
			l2=l1+k;
			u1=l2-1;
			u2=(l2+k-1<n)?l2+k-1:n-1;
			
			//合并后再將這個小數組排序成一個在序列
			for(i=l1,j=l2; i<=u1&&j<=u2; m++){
				
				if(a[i]<=a[j]){
					swap[m]=a[i];
					i++;
				}else{
					swap[m]=a[j];
					j++;
				}
			}
			
			
			//將子數組的其他元素放入swap數組中
			while(i<=u1){
				swap[m]=a[i];
				m++;
				i++;
				
			}
			
			while(j<=u2){
				swap[m]=a[j];
				m++;
				j++;
					
			}
			
			l1=u2+1;
			
		}
		//把沒有合并的照列寫入數組中.
		for(i=l1;i<n;i++,m++) swap[m]=a[i];
		
	}
}