병합 정렬(Merge Sort)

"병합 정렬"

     : 일단 정확히 반으로 나누고 나중에 정렬

 

• 시간 복잡도 : O(N * logN)
• 정확히 반으로 나누기 때문에, 최악의 경우에도 O(N * logN)을 보장
• 단계의 크기 : logN (데이터 개수 : N)
  정렬 자체에 필요한 수행 시간 : N

 

• 대표적인 '분할 정복' 방법을 채택한 알고리즘
• 재귀함수로 구현

 

• 합치는 순간에 정렬을 수행
• 반드시 정렬에 사용되는 배열은 '전역 변수'로 선언해야 함

 

• 기존의 데이터를 담을 추가적인 배열 공간이 필요하기 때문에, 메모리 활용이 비효율적
• 어떠한 상황에서도 정확히 O(N * logN)을 보장하기 때문에 몹시 효율적

 

class Sort {

	int[] sorted = new int[10]; // 임시적인 정렬 배열; 반드시 전역 변수로 선언



	public void merge (int arr[], int m, int middle, int n) {
    
		int i = m;
		int j = middle + 1;
		int k = m;
        
        
		while (i <= middle && j <= n) { // 작은 순서대로 배열에 삽입
        
			if (arr[i] <= arr[j]) {
				sorted[k] = arr[i];
				i++;
			}
			else {
				sorted[k] = arr[j];
				j++;
			}
            
			k++;
		}
        
        
		// 남은 데이터 삽입
		if (i > middle) {
			for (int t = j; t <= n; t++) {
				sorted[k] = arr[t];
				k++;
			}
		}
		else {
			for (int t = i; t <= middle; t++) {
            
				sorted[k] = arr[t];
				k++;
			}
		}
       
       
		for (int t = m; t <= n; t++) // 정렬 배열을 실제 배열에 삽입
			arr[t] = sorted[t];
	}
    
    
    
	void mergeSort (int arr[], int m, int n) {
    
		if (m < n) { // 원소가 2개 이상인 경우
        
			int middle = (m + n) / 2;
            
			mergeSort (arr, m, middle);
			mergeSort (arr, middle + 1, n);
			merge (arr, m, middle, n);
		}
}