[C/C++] 병합 정렬(merge sort) 원리와 오름차순구현

병합 정렬이란?

병합 정렬(merge sort) 또는 합병 정렬은 분할 정복 알고리즘의 하나로 원소를 분할하여 비교 및 정렬하는 알고리즘이다.

퀵 정렬은 피봇이라는 기준값이 있는 반면에, 병합 정렬은 피봇없이 일단 분할하는 방식이다.

 

예를 들어 다음과 같이 무작위로 섞어놓은 배열이 있습니다.

5 6 10 4 3 8 7 1

 

각 원소를 1나 씩 분할하는 것으로 시작합니다. 각 리스트의 길이가 1 될 때까지 분할합니다.

5	6	10	4	3	8	7	1

각 리스트는 길이가 1이므로 정렬된 것으로 봅니다.

 

이제 분할된 원소는 이웃한 원소 끼리 비교하며 병합합니다.

5	6	10	4	3	8	7	1

5 6	4 10	3 8	1 7

5와 6 비교, 10과 4 비교, 3과 8 비교, 7과 1 비교하여 길이가 2인 리스트 4개를 만듭니다.

 

계속해서 비교정렬, 병합 과정을 거치면 정렬이 완료됩니다.

5 6	4 10	3 8	1 7

4 5 6 10	1 3 7 8

1 3 4 5 6 7 8 10

 

5 6    4 10 이 합쳐지는 과정을 자세히 보겠습니다. 길이가 2인 리스트 2개를 길이가 4인 리스트 1개로 병합해야 합니다.

5를 가리키는 인덱스를 i, 4를 가리키는 인덱스를 j, 길이가 4인 리스트의 인덱스를 k라고 합시다. 각 리스트는 이미 정렬이 끝난 상태입니다.

 

i와 j를 비교하여 작은 값인 4를 먼저 정렬시키고 k는 k+1, j는 j+1 해서 10을 가리키게 됩니다.(4)

다시 i와 j를 비교하여 작은 값인 5를 정렬시키고 k는 k+1, i는 i+1 해서 6을 가리키게 됩니다.(4 5)

다시 i와 j를 비교하여 작은 값인 6을 정렬시키고 k는 k+1, i는 i+1 해서 범위를 벗어나게 됩니다.(4 5 6)

한쪽이 범위를 벗어나게 되면 남아있는 원소를 그대로 넣어줍니다. i, j 배열은 이미 정렬이 끝난 상태이기 때문에 바로 병합해 줍니다.(4 5 6 10)

 

그리고 k인덱스가 있는 임시 저장용 배열에 저장된 값을 원래 배열에 넣어줍니다.

 

#include <stdio.h>

int temp_arr[9];

void merge(int *arr, int start, int middle, int end){
	int i = start;
	int j = middle + 1;
	int k = start;
	
	//비교하여 데이터정렬 및 삽입
	while(i<=middle && j<=end){
		if(arr[i]<=arr[j]) temp_arr[k] = arr[i++];
		else temp_arr[k] = arr[j++];
		k++;
	}
	
	//남은 데이터 삽입
	if(i>middle){
		for(int t=j;t<=end;++t){
			temp_arr[k] = arr[t];
			++k;
		}
	}
	else{
		for(int t=i;t<=middle;++t){
			temp_arr[k] = arr[t];
			++k;
		}
	}
	
	//임시 저장용 배열에 저장된 값을 원래 배열에 넣어줌
	for(int t=start;t<=end;++t){
		arr[t] = temp_arr[t];
	}
}


void mergeSort(int *arr, int start, int end){
	//크기가 1 일대 까지 호출, 1단위 까지 쪼갬
	if(start < end){
		int middle = (start + end) / 2;
		mergeSort(arr, start, middle);
		mergeSort(arr, middle+1, end);
		//다시 병합
		merge(arr, start, middle, end);
	}
}
int main(){
	
	int i;
	//무작위 배열
	int arr[8] = {5, 6, 10, 4, 3, 8, 7, 1};
	
	//배열, 배열시작위치 0, 배열 마지막위치 7 
	mergeSort(arr, 0, 7);
	
	//출력 
	for(i=0;i<8;++i){
		printf("%d ", arr[i]);
	}
	
	return 0;
}

 

결과값:

1 3 4 5 6 7 8 10

 

병합 정렬은 피봇을 기준으로 나누는 대신에 일단 무조건 나누면서 시작을 했다. 따라서 피봇에 따라 시간 복잡도가 달라지는 퀵 정렬과 달리 병합 정렬은 시간 복잡도를 보장한다. 하지만 데이터의 양이 커지면 그만큼 임시로 저장할 배열을 크게 해야 한다는 점에서 메모리 활용이 비효율적임을 기억해야 한다.

 

 

병합 정렬의 시간 복잡도(or 빅오)는 O(N*log(N))입니다.