정렬 (9) - 병합 정렬 (Merge Sort)

1. 알고리즘 개요

• 병합(Merge) : 두개 이상의 정렬된 자료를 하나로 합치는 것

• 런(Run) : 병합할 하나의 단위를 런(Run)이라고 부름.

• 병합방법 : 런(Run)들이 정렬된 상태이므로 가장 앞 원소(가장 작음)를 비교해서 병합하면 됨

• 시간 복잡도 : $O(n logn)$, 최악의 경우에도 $O(nlogn)$의 시간복잡도가 보장되지만, 추가 배열을 항상 만들기 때문에 공간복잡도가 좋지 못함.

 

2. 병합 (Merge)

• 정렬된 두 런(Run)이 있을 때 각 런의 앞 원소를 비교해 작은 값을 결과배열에 담는 방식.

• 아래 애니메이션을 보면 직관적으로 이해할 수 있음.

 

 

3. 소스코드

#include<stdio.h>

void merge(int *arr, int l, int r){
	int mid = (l + r) / 2;
	int temp[r];
	
	int lp = l; // 왼쪽 시작 
	int rp = mid + 1; // 오른쪽 시작
	int tp = 0; // temp 포인터 
	
	while(lp <= mid && rp <= r){
	// 두 배열 모두 안끝났을 경우
		if(arr[lp] <= arr[rp]){
			temp[tp] = arr[lp]; // 더 작은 원소 기록
			lp++; tp++;
		} else{
			temp[tp] = arr[rp]; // 더 작은 원소 기록
			rp++; tp++;
		}
	}
	
	while(lp <= mid){
	// 왼쪽 배열 안끝났을 경우
		temp[tp] = arr[lp];
		lp++; tp++; 
	}
	
	while(rp <= r){
	// 오른쪽 배열 안끝났을 경우
		temp[tp] = arr[rp];
		rp++; tp++; 
	}
	
	for(int i = 0 ; i < tp ; i++){
	// 원본 배열에 기록 
		arr[l + i] = temp[i];		
	}
}

void merge_sort(int *arr, int l, int r){
	
	if(l < r){
		int mid = (l + r) / 2;
		
		merge_sort(arr, l, mid);
		merge_sort(arr, mid+1, r);
		merge(arr, l, r);
	}
}

void merge_sort(int *arr, int size){
	merge_sort(arr, 0, size-1);
}

int main(){
	int arr[] = {1, 2, 3, 2, 5, 0, 4, 6, 8, 7, 9};	
	int size = sizeof(arr)/sizeof(arr[0]);

	merge_sort(arr, size);
	
	for(int i = 0 ; i < size ; i++){
		printf("%d ", arr[i]);
	}
	
	return 0;
}

 

4. Reference