Merge Sort

Concept

배열을 둘로 나눈다. 나눈 배열을 또 둘로 나눈다. 배열방이 2개씩 남았을때 Merge Sort를 할 수 있다.

Partition이 방 한개씩 딱 두개의 배열로 나눌 수 있을때 데이터를 가지고 병합을 한다.

끝의 제일 작은 부분부터 이렇게 병합해가면서 정렬된 배열을 Merge해 나가는 방법.

적용

함수가 호출될 때마다 절반씩 잘라서 재귀적으로 함수를 호출하고 맨 끝의 제일 작은 조각부터 두개씩 병합해서 정렬된 배열을 Merge해 나간다

Time complexity (시간 복잡도)

• Binary search에서 검색 영역이 절반씩 떨어지는 것과 같은 원리
• 물리적으로 가운데값으로 partition을 나눈다
• 최악의 경우 - O(n Log n)
  • Quicksort로 따지면 pivot을 잘 골랐을 때와 같다
• 공간을 사용 할 수 없는 경우에는 quicksort를 이용해야 한다

Merge Sort 구현

public class Test {
	private static void mergeSort(int[] arr) {
		// 임시 저장 공간이 필요하다
		int[] tmp = new int[arr.length]; 
		mergeSort(arr, tmp, 0, arr.length-1);  // 재귀 호출 시작
	}

	private static void mergeSort(int[] arr, int[] tmp, int start, int end){
		if(start < end){
			// 함수가 호출되면 배열을 가운데로 자른다
			int mid = (start + end) / 2;  
			mergeSort(arr, tmp, start, mid);
			mergeSort(arr, tmp, mid +1, end);
			// 재귀함수가 돌아온 다음에는 합쳐줘야한다
			// 이때는 가운데를 기준으로 왼쪽과 오른쪽이 정렬이 되어있는 상태
			// 두개로 나뉘어 있는 배열 방을 Merge
			merge(arr, tmp, start, mid, end);
		}
	}

	private static void merge(int[] arr, int[] tmp, int start, int mid, int end){
		// 임시 저장소에 필요한 만큼 배열을 복사해준다
		for (int i = start; i <= end; i++){
			tmp[i] = arr[i];
		}
		int part1 = start;       // 첫 번째 배열 방의 첫번째 인덱스
		int part2 = mid + 1;     // 두 번째 배열 방의 첫번째 인덱스
		int index = start;
		while(part1 <= mid && part2 <= end){. // 첫 번째 배열의 끝이나 두 번째 배열의 끝에 다다르면 
			if(tmp[part1] <= tmp[part2]) {
				arr[index] = tmp[part1];
				part1++;
			} else {
				arr[index] = tmp[part2];
				part2++;
			}
			index++;
		}
		// 앞쪽 배열에 데이터가 남아있는 경우, 뒤쪽 배열은 비어있다
		for (int i=0; i <= mid - part1; i++){
			arr[index + i] = tmp[part1 + i];
		}
		// 앞쪽 배열은 비어있고, 뒤쪽 배열에 데이터가 남아있는 경우
		
	}

	private static void printArray(int[] arr){
		for(int data : arr){
			System.out.println(data + ", ");
		}
		System.out.println();
	}

	public static void main(String[] args){
	int[] arr = {3,9,4,7,5,0,1,6,8,2};
	printArray(arr);
	mergeSort(arr);
	printArray(arr);
	}
}