並べ替えアルゴリズムの集計並べ替えJava版

/**
 *                        ,                   ，           。
 *          ，         
 *       O(nlogn)
 *       O(n)       n             
 *       ：
 *               ，，          。
 *                 ，            。
 *     ，                 。
 * 
 */
public class MergeSort {
	public void sort(int[] arr){
		sort(arr, 0, arr.length - 1);
	}
	
	private void sort(int[] arr, int start, int end){
		if(start >= end){
			return;
		}
		
		int middle = (start + end) / 2;
		sort(arr, start, middle);
		sort(arr, middle + 1, end);
		merge(arr, start, middle, end);
	}
	
	/**
	 *           
	 * @param arr   
	 * @param start         
	 * @param middle         ，middle+1         
	 * @param end         
	 */
	private void merge(int[] arr, int start, int middle, int end){
		//      
		int tmplen = end - start + 1;
		
		//    
		int[] tmp = new int[tmplen];
		
		//       
		int left = start;
		
		//       
		int right = middle + 1;
		
		//tmp     
		int i = 0;
		
		while(left <= middle && right <= end){
			if(arr[left] < arr[right]){
				tmp[i] = arr[left];
				left++;
			}else{
				tmp[i] = arr[right];
				right++;
			}
			
			i++;
		}
		
		while(left <= middle){
			tmp[i] = arr[left];
			left++;
			i++;
		}
		
		while(right <= end){
			tmp[i] = arr[right];
			right++;
			i++;
		}
		
		for(i = 0; i < tmplen; i++){
			arr[start + i] = tmp[i];
		}
	}
}