병합 정렬

병합 정렬: 모든 원소들이 하나로 남을때까지 정확하게 절반으로 나눈 후 나중에 합쳐서 정렬하는 알고리즘.

 

Ex)

(이미 하나까지 전부 반으로 쪼게진 상태라 가정하고 2의 배수만큼 차례대로 합쳐진다.)

 

7 6 5 8 3 5 9 1

67 58 35 19

5678 1359

13556789

시간 복잡도: O(N*log N)

너비가 n이고 높이가 log n

(정렬이 되어있는 상태에서 데이터를 하나씩 읽어나가 새롭게 정렬을 하므로 n * log n에 비례.)

 

병합 정렬의 경우 항상 정확히 절반으로 분할되고 정복하는 과정이 반복되므로 최악의 경우에도 O(N*log N)을 보장한다. (퀵 정렬은 편향되게 분할 할 가능성이 있으므로 최악의 경우 O(N^2))

 

단점: 기존의 데이터를 담을 추가적인 배열 공간이 필요하여 메모리 활용이 비효율적임.

 

#include <stdio.h>

int n = 10;
int sorted_arr[10];
/* 병합 정렬에서는 추가적인 배열이 필요한데, 전역 변수로 배열을 선언하게 되면 모든 함수가 
 공통적으로 이용할 수 있기때문에 불필요한 메모리 사용을 최소화할 수 있다. */
			
void merge(int arr[], int start, int mid, int end);
void mergeSort(int arr[], int start, int end);

int main() {
	int arr[n] = {7, 6, 5, 8, 4, 5, 9, 2, 10, 1};
	mergeSort(arr, 0, n-1);
	for(int i = 0; i<n; i++) {
		printf("%d ",arr[i]);
	}
}

void merge(int arr[], int start, int mid, int end) {
	int i = start;
	int j = mid+1;
	int k = start;

	// 작은 순서대로 배열에 삽입.
	while(i<=mid && j<=end) {
		if(arr[i] <= arr[j]) {
			sorted_arr[k] = arr[i];
			i++;
		}
		else {
			sorted_arr[k] = arr[j];
			j++;
		}
		k++;
	} 

	// 남은 데이터도 삽입
	if(i > mid) {
		for(int t = j; t<=end; t++) {
			sorted_arr[k] = arr[t];
			k++;
		}
	} 
	else {
		for(int t = i; t<=mid; t++) {
			sorted_arr[k] = arr[t];
			k++;
		}
	}

	// 정렬된 배열을 실제 배열로 삽입 
	for(int t = start; t<=end; t++) {
		arr[t] = sorted_arr[t];
	}
} 

// 크기가 1일때까지 반으로 나누고 최종적으로 합쳐서 정렬
void mergeSort(int arr[], int start, int end) {  
	// 크기가 1보다 큰 경우
	if(start<end) {
		int mid = (start + end)/2;
		mergeSort(arr, start, mid);
		mergeSort(arr, mid+1, end); 
		merge(arr, start, mid, end);
	} 
}