Merge Sort

#

  특징

*propotion : 비례한

*in-place : 제자리에서

// 꽃댕댕
public class HelloWorld {

	/************************************
	주의 : arr[]의 크기를 엄청 크게 할 경우
	1. stack의 overhead때문에 연산이 수행되지 않을 수 있습니다.
	2. String[] args의 크기가 65535byte 밖에 입력되지 않아서 오류를 내뿜습니다.
	*************************************/

	public static void main(String[] args) {

		
		int arr[] = { 234, 45 , 563, 345, 345,
				234, 45 , 563, 345, 345,
				234, 45 , 563, 345, 345,
				234, 45 , 563, 345, 345,
				234, 45 , 563, 345, 345,
				234, 45 , 563, 345, 345,
				234, 45 , 563, 345, 345,
				};
		
		mergeSort(arr);
		print(arr);	
		
	}
	
	public static void print(int arr[]){
		
		for(int i = 0; i < arr.length; i++){
			System.out.print(arr[i] + " ");
		}
		
	}
	
	public static void mergeSort(int arrParent[]){
		if(arrParent.length < 2) return;
		
		int mid = arrParent.length / 2;
		int arrLeft[]  = new int[mid];
		int arrRight[] = new int[arrParent.length - mid];
		
		for(int i = 0; i < mid; i++){
			arrLeft[i] = arrParent[i]; 
		}
		
		for(int i = mid; i < arrParent.length; i++){
			arrRight[i-mid] = arrParent[i];
		}
		
		mergeSort(arrLeft);
		mergeSort(arrRight);
		merge(arrLeft, arrRight, arrParent);
		
	}
	
	public static void merge(int arrLeft[], int arrRight[], int arrParent[]){

		int left, right, parent;
		// i는 left의 인덱스, k는 right의 인덱스 p는 parent=0의 인덱스
		left = right = parent = 0;
		
		while(left < arrLeft.length && right < arrRight.length){
			//2개의 arr중 작은 값을 merge하는데, arrLeft[인덱스]의 값이 작은 경우.
			if(arrLeft[left] <= arrRight[right]){
				arrParent[parent] = arrLeft[left];
				left++;
				
			} 
			//2개의 arr중 작은 값을 merge하는데, arrRight[인덱스]의 값이 작은 경우.
			else {
				arrParent[parent] = arrRight[right];
				right++;
			}
			parent++;
		}
		
		while( left < arrLeft.length){
			arrParent[parent] = arrLeft[left];
			parent++;
			left++;
		}
		
		while( right < arrRight.length){
			arrParent[parent] = arrRight[right];
			parent++;
			right++;
		}
		
	}
	
}