50. 합병정렬

합병정렬이란?

퀵 정렬과 마찬가지로 분할 정복 알고리즘을 사용하여 리스트를 정렬하는 알고리즘이다.

리스트를 반으로 나눈 후, 각각을 재귀적으로 정렬하고 병합하여 최종적으로 정렬된 리스트를 생성한다.

 

동작 방식

1. 리스트를 반으로 나눈다. (길이가 1 이하가 될 때까지 재귀적으로 반복한다.)

2. 나누어진 각 부분 리스트에 대해 정렬을 수행한다.

3. 정렬된 부분 리스트들을 병합하여 한 개의 정렬된 리스트를 생성한다.

4. 재귀 호출이 완료되고 병합이 이루어진 후에는 정렬된 리스트가 반환된다.

 

합병 정렬은 리스트를 작은 부분으로 나누어 정렬하고 병합하기 때문에 안정적이고 효율적인 알고리즘이다.

항상 일정한 시간복잡도 O(n log n)을 보장하며, 대부분의 경우에서 다른 알고리즘보다 빠른 실행 속도를 보이지만,

리스트를 임시로 저장할 추가적인 메모리 공간이 필요하다는 단점이 존재한다.

---

// 배열을 정렬한다. 
void Merge(int User_Data[], int Merge_Array[], int i, int m, int n){
	int j=m+1, k=i, t;
	
	// 2개의 리스트를 비교하면서 다른 배열에 정렬한다. 
	while(i<=m && j<n){
		if(User_Data[i] <= User_Data[j]) Merge_Array[k++] = User_Data[i++];
		else Merge_Array[k++] = User_Data[j++];
	}
	
	// 하나의 리스트가 모두 정렬이 끝나면 정렬이 끝나지 않은 다른 리스트는 그대로 배열어 넣는다. 
	if(i>m) for(t=j;t<=n;t++) Merge_Array[t] = User_Data[t];
	else for(t=i;t<=m;t++) Merge_Array[k+t-i] = User_Data[t];
}

// 현 리스트에서 Segment에 따른 각각의 케이스를 확인하여 정렬을 진행한다. 
void Merge_case(int User_Data[], int Merge_Array[], int n, int s){
	int i, j;
	
	// 중간 과정을 출력합니다. (알고리즘과 무관) 
	// Merge_Print(User_Data, s, n);
	
	// case 1 : 2개의 리스트가 Segment 크기에 맞는 경우 
	for(i = 0; i<n-2*s+1; i+=2*s) Merge(User_Data, Merge_Array, i, i+s-1, i+2*s);
	// case 2 : 1개의 리스트는 Segment 크기에 맞고 다른 1개의 리스트는 Segment크기보다 작을 때 
	if((i+s) < n) Merge(User_Data, Merge_Array, i, i+s-1, n);
	// case 3 : 1개의 리스트만 존재하는 경우 
	else for(j=i; j<n; j++)	Merge_Array[j] = User_Data[j];
}

//  Segment 크기를 늘려가면서 정렬을 한다. 
void Merge_Sort(int User_Data[], int n){
	int i, s = 1, Temp_Data[n];
	
	// 배열을 2개 사용하므로 2번을 번갈아가면서 사용한다.
	// 만약 if문으로 처리하고 싶으면 마지막으로 했던 배열을 리턴해줘야 한다
	while(s < n){
		Merge_case(User_Data, Temp_Data, n, s);
		s *= 2;
		Merge_case(Temp_Data, User_Data, n, s);
		s *= 2;
	}
}