병합 정렬 / 합병 정렬 ( C언어)

병합 정렬의 기본 개념

1. 배열을 반으로 쪼갠다

2. 반으로 쪼갠 배열을 각각 또 반으로 쪼갠다.

3. 같은 방법으로 더 쪼갤 수 없을 만큼 쪼갠다

4. 쪼갠 배열을 순서에 맞춰 합친다

 

> 함수가 두 가지 필요하다. 배열을 반으로 나누는 함수, 그리고 그 나누어진 배열을 순서대로 맞추는 함수

void merge(int left, int right, int* arr){
	int mid = (left + right) /2;
    int right_first = mid + 1;
    int left_first = left;
    int temp_idx = left;
    int* temp[1000001];

    // 두 배열을 반으로 나누어 정렬 한다.
    while(left_first <= mid && right_first <= right){
    	// 왼쪽부터 순서대로 더 작은 값을 배치한다.
    	if(arr[left_first] <= arr[right_first]){
		temp[temp_idx++] = arr[left_first++];
        }else{
		temp[temp_idx++] = arr[right_first++];
        }
    }

    // 배치하면서 늘어난 left_first 인덱스가 mid값을 넘어선 경우
    if(left_first > mid){
    	// mid값 이후의 index를 temp에 넣어준다.
    	while(right_first <= right){
        	temp[temp_idx++] = arr[right_first++];
        }
    // 배치하면서 늘어난 left_first 인덱스가 mid값을 넘어서지 않은 경우
    }else{
    	// mid 값 이전의 index를 temp에 넣어준다.
    	while(left_first <= mid){
        	temp[temp_idx++] = arr[left_first++];
        }
    }
    
    // 배치한 temp값의 원소를 arr에 넣는다.
    while(left <= right){
    	arr[left] = temp[left];
        left++;
    }
}

// 계속 반으로 나누는 함수
void merge_sort(int left, int right, int* arr){
    int mid = (left + right ) / 2;
	
    if(left >= right) return;
    
    merge_sort(left, mid, arr);
    merge_sort(mid+1, right, arr);
    merge(left, right, arr);
}

 

기본 개념만 숙지해두고 이후는 코드를 보면서 이해하는게 편하다.

• merge 함수에는 반으로 잘린 인덱스들이 들어온다.
  • 계속 반으로 나누다보면 결국 left인덱스와 right 인덱스 차이가 1만 나는 인덱스가 들어올것이다
  • merge에서 둘중 더 작은것을 왼쪽으로 보낸다(정렬이 하나 완성됐다)
  • 재귀가 하나 끝나고 밖으로 나와보면 완성된 두개의 배열을 맞이하게 된다.
  • 이 배열은 각각 정렬된상태여서 같은 방법을 적용시키면 더욱 길어진 정렬된 배열을 가질 수 있다.
  • 차근차근 이렇게 정렬시키다보면 결국 O(NlogN)의 시간복잡도를 보장할 수 있다.