（排序算法二）合并排序

自己写的，欢迎拍砖！

public class MergeSort {

	/**
	 * 合并排序
	 * @param args
	 */
	public static void main(String[] args) {
		int[] sourceArray = {22,428,23,76,24,4,52,45,6,56,13,75,76,9,6,342,5,67};
		MergeSort is = new MergeSort();
		int[] targetArray = is.sort(sourceArray);
		for (int i = 0; i < targetArray.length; i++) {
			int j = targetArray[i];
			System.out.println(j);
		}
	}
	
	private int[] sort(int [] sourceArray){
		
		merge_sort(sourceArray, 0, sourceArray.length-1);
		return sourceArray;
	}
	
	private void merge_sort(int[] source, int begin, int end){
		if(begin < end){
			int middle = (begin + end)/2;
			merge_sort(source, begin, middle);
			merge_sort(source, middle+1, end);
			merge(source, begin, end, middle);
		}
	}

	private void merge(int[] source, int begin, int end, int middle) {
		/**
		 * 分成两个数组left,right之间的合并
		 * 并分别用i,j来记录比较的位置
		 */
		int m = middle - begin + 1;
		int n = end - middle;
		int[] left = new int[m];
		int[] right = new int[n];
		
		for (int i = 0; i < left.length; i++) {
			left[i] = source[begin + i];
		}
		for (int i = 0; i < right.length; i++) {
			right[i] = source[middle + i + 1];
		}
		
		int i,j,k=begin;
		//开始逐位比较左右两个有序的数据大小
		for(i=0,j=0; i<m && j<n; k++){
			if(left[i] > right[j]){
				source[k] = right[j];
				j++;
			}else{
				source[k] = left[i];
				i++;
			}
		}
		//其中有一们已经比完了，剩下的直接添加到source中就可以了
		while(i<m){
			source[k] = left[i];
			k++;
			i++;
		}
		while(j<n){
			source[k] = right[j];
			k++;
			j++;
		}
	}
}