Mergesort.java

class Mergesort{
	public static void main(String ... args){
		int [] array= {5, 4, 3, 2, 1, 0};
		printArray(mergerSort(copyOf(array,0, array.length)));
	}

	static void printArray(int [] array){
		for(int i: array){
			System.out.print(i+" ");
		}
		System.out.println();
	}

	static int [] copyOf(int [] array, int f, int l){
		int [] arr= new int [l-f];
		for(int j=0; f<l; f++, j++)
			arr[j]=array[f];
		return arr;
	}

	static int [] joinArray(int [] arr1, int [] arr2){
		int [] array= new int[arr1.length+arr2.length];
		for(int i=0; i<array.length; i++){
			array[i]=(i<arr1.length)?arr1[i]:arr2[i-arr1.length];
		}
		return array;
	}

	static int [] mergerSort(int [] array){
		if(array.length<=1){
			return array;
		}
		int m= (array.length)>>1;
		int [] arr1= mergerSort(copyOf(array, 0,m));
		int [] arr2= mergerSort(copyOf(array, m, array.length));
		int [] arr= new int[arr1.length+arr2.length];
		int i=0, j=0, k=0;
		while(i<arr1.length && j<arr2.length){
			if(arr1[i]<arr2[j]){
				arr[k]=arr1[i++];
			}else{
				arr[k]=arr2[j++];
			}
			k++;
		}

		while(i<arr1.length){
			arr[k]=arr1[i++];
			k++;
		}
		while(j<arr2.length){
			arr[k]=arr2[j++];
			k++;
		}
		return arr;
	}
}