import java.util.Arrays;


public class Merge {
	public Merge(){
		
	}
	
	public void sort(int[] array){
		if(array.length > 1){
			int half = array.length/2;
			int[] a1 = Arrays.copyOfRange(array, 0, half);
			int[] a2 = Arrays.copyOfRange(array, half, array.length);
			sort(a1);
			sort(a2);
			merge(array, a1, a2);
		}
	}
	
	private void merge(int[] array, int[] a1, int[] a2){
		int len1 = a1.length;
		int len2 = a2.length;
		int it1 = 0;
		int it2 = 0;
		
		for(int i=0; i < array.length; i++){
			if(it2==len2 || (it1 < len1 && a1[it1] < a2[it2])){
				array[i] = a1[it1];
				it1++;
			}
			else{
				array[i] = a2[it2];
				it2++;
			}			
		}	
	}
}