합병 정렬 (Merge sort)

Quick Sort와 함께 대표적으로 사용되는 빠른 정렬 알고리즘이다.

시간 복잡도는 O(n log n)을 가진다.

 

합병 정렬은 3가지의 과정을 가진다.

1. 분할
   • N 길이의 배열은 N / 2 길이의 배열 2개로 분할 시켜 나간다.
2. 정복
   • 부분 배열의 크기가 충분히 작아질 때까지 재귀 호출을 반복한다. 그 후 부분 배열을 정렬한다.
3. 결합
   • 정렬된 부분 배열을 결합하여 완성된 배열을 만들어 낸다.

출처 https://dpdpwl.tistory.com/53

출처 https://dpdpwl.tistory.com/53

 

구현하기

define MAX_SIZE 20

int arr[MAX_SIZE];
int *arr2;

void merge(int left, int right){

    int mid = (left + right) / 2;
    
    int i = left;
    int j = mid + 1;
    int k = left;
    while(i <= mid && j <= right){
    	if(arr[i] <= arr[j]
        	arr2[k++] = arr[i++];
        else
        	arr2[k++] = arr[j++];
    }
    
    int temp = i > mid ? j : i;
    
    while(k<=right) arr2[k++] = arr[temp++];
    
    for(int i = left; i <= right; i++) arr[i] = arr2[i];
    
}

void mergeSort(int left, int right){

    int mid;
    if( left < right ){
    	mid = (left + right) / 2;
        mergeSort(left, mid);
        mergeSort(mid + 1, right);
        merge(left, right);
    }
}

int main(){
	
    int x;
    cin >> x;
    arr2 = new int[x];
    for(int i = 0; i < x; i++) 
    	cin >> &arr[i];
    
    mergeSort(0, x-1);
    
    for(int i=0; i < x; i++)
    	cout << arr[i] << " ";
}
    
}