[자바 이클립스] 병합정렬

전체 원소를 분할하여 정렬한 뒤 병합하는 방식

 

1. 정렬할 데이터 집합을 절반으로 나눈다(재귀 - 하위 데이터(leaf) 크기가 1일 때 까지)

 

2. 하위 데이터 2개를 정렬하고 병합한다

 

* O(nlogn)의 시간 복잡도를 가진다.

* O(n) 크기의 임시 배열 공간이 필요하다.

 

	private static void mergeSort(int[] arr) {
		int[] tmp = new int[arr.length]; // 임시저장공간
		mergeSort(arr, tmp, 0, arr.length -1); // 재귀, start=0 end=arr.length-1
	}
	
	private static void mergeSort(int[] arr, int[] tmp, int start, int end) { // 배열, 임시저장, 시작, 끝 
		
		if(start<end) { // start와 end는 처음과 끝 값을 대표하는 인자 
			
			int mid = (start + end) / 2; 
			System.out.println("여기 0"+","+start+","+mid+","+end); 
			
			mergeSort(arr, tmp, start, mid); 
			// mid가 0까지 작아져 다음 코드로 넘어감 
			// mergeSort 안에 mergeSort 가 속해있는 개념으로 사이클이 돈다.. 
			System.out.println("전반부"+","+start+","+mid+","+end); 
			
			mergeSort(arr, tmp, mid+1, end);
			System.out.println("후반부"+","+start+","+mid+","+end); 
			
			merge(arr, tmp, start, mid, end);
			System.out.println("합침"+","+start+","+mid+","+end); 
			System.out.println();
		
		}