[Sorting] 2. Merge Sort

2. Merge Sort

Space-Complexity = 입력 배열 크기의 보조 메모리를 사용한다.

Time-Complexity = O(n log n)

원리

기본적인 개념으로는 n개의 원소를 가진 배열을 정렬할 때, 정렬하고자 하는 배열의 크기를 작은 단위로 나누어 정렬하고자 하는 배열의 크기를 줄이는 원리를 사용한다. Divide and conquer라는, 분할하여 정복한다의 원리인 것이다. 말 그대로 복잡한 문제를 복잡하지 않은 문제로 분할하여 정복하는 방법이다. 단 분할(divide)해서 정복했으니 정복(conquer)한 후에는 결합(combine)의 과정을 거쳐야 한다.

 

Merge Sort는 더이상 나누어지지 않을 때 까지 반 씩(1/2) 분할하다가 더 이상 나누어지지 않은 경우에는 ( 원소 하나인 배열일 때가 되겠다. ) 자기 자신, 즉 원소 하나를 반환한다. 원소가 하나인 경우에는 정렬할 필요가 없기 때문이다. 이 때 반환한 값끼리 combine될 때, 비교가 이뤄지며, 비교 결과를 기반으로 정렬되어 임시 배열에 저장된다. 그리고 이 임시 배열에 저장된 순서를 합쳐진 값으로 반환한다. 실제 정렬은 나눈 것을 병합하는 과정에서 이뤄지는 것이다.

결국 하나씩 남을 때까지 분할하는 것이면, 바로 하나씩 분할해버리면 되지 않을까? 재귀적으로 정렬하는 원리인 것이다. 재귀적 구현을 위해 1/2씩 분할한다. 

c code>

void merge_sort(int * arr, int left, int right) {
    if(arr == NULL) return ;//Error return
    if(left >= right) return ;//recursive terminated condition
    
    int mid = left + (right - left)/2;
    
    merge_sort(arr, left, mid);
    merge_sort(arr, mid+1, right);
    
    merge(arr, left, mid, right);
}

//merge
void merge(int * arr, int left, int mid, int right) {
    if(arr == NULL) return ;
    int * sortedArr = (int*)malloc(sizeof(int)*(right+1)); // 정렬된 배열을 임시로 저장하고 있을 배열
    int leftArrIdx = left; // 좌측 배열의 첫번재 인덱스 값
    int rightArrIdx = mid + 1; // 우측 배열의 첫번째 인덱스 값
    int sortedArrIdx = left; //정렬된 배열을 임시로 저장하고 있을 배열의 첫번째 인덱스 값
    
    while(leftArrIdx <= mid && rightArrIdx <= right) { //좌측 배열 또는 우측 배열 둘 중 한 배열의 끝까지 반복
        if(arr[leftArrIdx] <= arr[rightArrIdx]){//좌우측 배열의 원소 비교하여 작은 값을 임시 배열에 저장
            sortedArr[sortedArrIdx++] = arr[leftArrIdx++];//두 배열의 인덱스 값 증가
        } else {
            sortedArr[sortedArrIdx++] = arr[rightArrIdx++];//두 배열의 인덱스 값 증가
        }
    }
    
    if(leftArrIdx > mid) {//left array에 있는 원소를 모두 정렬했는데 right array가 아직 다 정렬이 안된 경우
        for(int i = rightArrIdx; i <= right; i++, sortedArrIdx++){
            sortedArr[sortedArrIdx] = arr[i];
        }
    } else {//right array에 있는 원소를 모두 정렬했는데 left array가 아직 다 정렬이 안된 경우
        for(int i = leftArrIdx; i <= mid; i++, sortedArrIdx++){
            sortedArr[sortedArrIdx] = arr[i];
        }
    }
    //본래의 배열을 정렬된 배열로 바꿔준다.
    for(int i = left; i <= right; i++)
        arr[i] = sortedArr[i];
    
    free(sortedArr);//임시 배열을 메모리에서 free 해준다.
}

2. the end