class Util{

    
    public static int[] mergeSort(int []t){	
	return mergeSortaux(t,0,t.length-1);
    }


    public static int[] mergeSortaux(int[] t, int i, int j){
	//retourne tableau trié correspondant à t entre indices i et j compris
	//i <= j
	if(j >= i+1){
	    int m = (i+j)/2;
	    int[] t1 = mergeSortaux(t,i,m);
	    int[] t2 =  mergeSortaux(t,m+1,j);
	    return merge(t1,t2);
	}
	int[] res = new int[1];
	res[0] = t[i];
	return res;
    }

    public static int[] merge(int[]t1, int[]t2){
	int[] res = new int[t1.length+t2.length];
	int i = 0;
	int j = 0;


	for(int x = 0; x < res.length;x++){
	    if(i==t1.length){
		res[x] = t2[j];
		j++;
	    }
	    else if (j==t2.length){
		res[x] = t1[i];
		i++;
	    }
	    else{
		if(t1[i] < t2[j]){
		    res[x] = t1[i];
		    i++;
		}
		else{
		    res[x] = t2[j];
		    j++;
		}
	    }
	}
	return res;
    }

}