// Create by Inho 2018. 4. 3. 오후 6:11:11
// 합병정렬

/***
* 시간 복잡도 최악O(nlogn), O(nlogn)
* 분할정복법(Divide-And-Conquer)
* 퀵이랑 비슷하지만 이건 리스트의 길이를 쪼갠후에
* 정렬하면서 합병(merge)한다. 
* 이미 쪼개진 데이터를 정렬하면서 합병하는 부분을 재귀를 사용하여 길이가 n인 리스트로 구성한다
*/

public class Study_Merge_Sort {
	public static void main(String[] args) {
	
		Study_Merge_Sort study = new Study_Merge_Sort();
		
		int data[] ={5,4,3,2,1,11};
		
		study.mergeSort(data,0,data.length-1);
		
		for (int i = 0; i < data.length; i++) {
			System.out.println("data["+i+"] : "+data[i]);
		}
	}
	
	public void mergeSort(int[] data, int left, int right){
		if(left < right){
			int pivot = (left + right)/2;		// divide 할 pivot 구하기
			mergeSort(data,left, pivot);		// 재귀를 통해 리스트의 길이가 더 나눌 수 없을때까지 나눔.
			mergeSort(data,pivot+1,right);
			merge(data,left,pivot,right);		// 그러고 배열 안에서 정렬을하면서 합침.(배열안에서 정렬만 한다고 볼 수있다.)
		}
	}
	
	public void merge(int[] data, int left, int pivot, int right){
//		완전 대체를 해야함.
		int i=left, j=pivot+1, k=left;				// 주어진 데이타와 같은 크기의 배열을 선언하고, 정렬에 필요한 변수도 따로 선언
		int[] temp = new int[data.length];
		while(i<=pivot && j <= right){
			if(data[i]<=data[j])
				temp[k++] = data[i++];		// 맨 왼쪽값이 pivot값 보다 작으면 똑같이 복사한 배열에 맨왼쪽에 넣어준다.(반복)
			else
				temp[k++] = data[j++];		// 오른쪽에선 pivot값이 맨 오른쪽 값보다 작으면 pivot인덱스의 값을 넣어준다. 
		}
		while(j<=right)						// 둘 중 어느 한쪽이 먼저 끝나면 복사 배열에 남은 값들을 넣어준다.
			temp[k++] = data[j++];
		while(i<=pivot)						// ..
			temp[k++] = data[i++];
		for(int l=left;l<=right;l++)		// 같은 크기로 복사하고 정렬을 마친 배열을 data에 넣어준다.
			data[l] = temp[l];
	}
}