병합정렬 학습내용

병합정렬을 6번정도 본 것 같지만 여전히 머리속에 남질 않는다.
좀더 잘 병합정렬을 이해하기위해 임의의 배열을 설정하고 가장 작게 나눠질 때 까지 배열을 나눠 보았다.

#include <stdio.h>

int number = 8;
int sorted[8]; //정렬 배열을 바드시 전역 변수로 선언

void merge(int a[], int m, int middle , int n){
	int i = m;
	int j = middle + 1;
	int k = m;
	//작은 순서대로 배열에 삽입
	
	while(i <= middle && j <= n){
		if(a[i] <= a[j]){
			sorted[k] = a[i]
			i++
		}
		if(a[i] > a[j]){
			sorted[k] = a[j];
			j++
		}
		k++;
	}
	//남은 데이터도 삽입
	if( i> middle){
		for(int t = j; t <=n; t++){
			sorted[k] = a[t];
			k++;
			}
	}
	for( int t = m; t <= n; t++){
		a[t] = storted[t];
	}
} 

void mergeSort(int a[], int m, int n){
	
	if(m < n){
		int middle = (m + n) /2;
		mergeSort(a, m,  middle);
		mergeSort(a, middle + 1, n);
		merge(a, m, middle, n);
	}
}

배열의 크기를 6으로 작고 가장 작게 나눠질 때 까지한다고 가정해 보자

mergeSort(a,0,5)는

mergeSort(a,0,2) 와 mergeSort(a,3,5)로 나뉜다

mergeSort(a,0,2)는

mergeSort(a,0,1)과 mergeSort(a,2,2)로 나뉘고

mergeSort(a,0,1)은

mergeSort(a,0,0)과 mergeSort(a,1,1)로 나뉘고 더이상 나눠지지 않는다.
여기서 merge가 일어난다.
그리고 머지가 일어난뒤 mergeSort(a,2,2)가 실행되는데 여기서는 더 나뉘지지 않는다.
내가 생각한 병합정렬은 0,1이 합쳐진 것과 2,3이 합쳐진 것이여야 했지만
여기서는 0,1이 합쳐진 것과 2와 다시 합쳐진다.

그 이유를 공곰히 생각해 봤는데 a의 배열을 반으로 나누면
3, 3이기 각각이 홀수 이기 때문이다
만약 배열의 크기가 8이였다면 4,4 였기 때문에 내가 처음 생각한 데로 0,1 + 2,3이 되었을 거다

그렇다면 이렇게 나뉘어질때 갯수가 홀수 개가 되는 것은 시간 복잡도가 nlogn이 됨에 영향이 없는건가?

2024/9/24
1. 계속해서 짝수로 나눠지는 경우의 수는 2의 거듭제곱인 것 같다.
배열 함수가 그렇듯 어느 경우의 수에는 그 함수의 시간복잡도 보다 빠르게 계산되거나 느리게 계산 될 수 도 있다는 것이다.
2. 일단 이해하기로는 깊이가 logn이기 때문인 건 알겠는데 뭔가 수학적으로 완전히 이해가 되지 않는것 같다.