[Algorithm] 정렬 - Merge Sort (합병 정렬)

Merge Sort

• 원소 개수가 1개 또는 0개가 될 때까지 반으로 나눈뒤 반으로 나눈 원소들을 합쳐가는 과정에서 정렬하는 방식
• 정렬하려는 배열 크기만큼의 추가 배열이 필요함
• \(O(nlogn)\)으로 \(O(n^2)\)인 Selection, Insertion, Bubble Sort보다 훨씬 빠름
• Divide And Conquer 알고리즘

• 

동작

Merge가 동작하는 시점?을 하나의 Step으로 본다.

Step 1

 

Step 2

 

Step 3

 

Step 4

 

Step 5

 

Step 6

코드

public class Sort {
	
    public void mergeSort(int[] arr, int first, int last) {
    	if(first < last) {
        	int mid = (first + last) / 2;
            mergeSort(arr, first, mid);
            mergeSort(arr, mid + 1, last);
            merge(arr, first, mid, last);
        }
    }
    
    public void merge(int[] arr, int first, int mid, int last) {
    	int i = first;
        int j = mid + 1;
        int k = first;
        int[] copy = new int[arr.length];
        
        while(i <= mid && j <= last) {
        	if(arr[i] > arr[j]) {
            	copy[k++] = arr[j++];
            } else {
            	copy[k++] = arr[i++];
            }
        }
        
        if(i > mid) {
        	for(int l = j; j <= last; j++) {
            	copy[k++] = arr[l];
            }
        } else {
        	for(int l = i; i <= mid; i++) {
            	copy[k++] = arr[l];
            }
        }
        
        for(int l = first; l <= last; l++) {
        	arr[l] = copy[l];
        }
    }
    
}

 

왜 \(O(nlogn)\)일까?