归并排序

摘自百度百科的代码- -

public static void main(String args[]){
		int[] a = {5,3,6,2,1,9,4,8,7};
		System.out.println(Arrays.toString(merge(a)));
	}

	public static int[] merge(int[] array){
		
		if(array.length == 1){
			return array;
		}else{
			
			int center = array.length / 2;
			int[] arrayL = new int[center];
			int[] arrayR = new int[array.length - center];
			
			for(int i = 0; i < center; i++){
				arrayL[i] = array[i];
			}
			
			for(int i = center, j = 0; i < array.length; i++, j++){
				arrayR[j] = array[i];
			}
			arrayL = merge(arrayL);
			arrayR = merge(arrayR);
			return sort(arrayL, arrayR);
			
		}
			
	}
	
	
	public static int[] sort(int[] arrayL, int[] arrayR){
		
		int[] result = new int[arrayL.length + arrayR.length];
		
		int i = 0;
		int j = 0;
		
		int resultIndex = 0;
		
		while(i < arrayL.length && j < arrayR.length){
			
			if(arrayL[i] < arrayR[j]){
				result[resultIndex++] = arrayL[i++];
			}else{
				result[resultIndex++] = arrayR[j++];
			}
		}
		for(int k = i; k < arrayL.length; k++){
			result[resultIndex++] = arrayL[k];
		}
		for(int k = j; k < arrayR.length; k++){
			result[resultIndex++] = arrayR[k];
		}
		
		return result;
	}