Merge Sort

Merge Sort

void merge(int arr[], int left, int mid, int right){
    int i = left;
    int j = mid+1;
    int idx = left;
 
    while(i <= mid && j <= right){
        if(arr[i] < arr[j]){
            outPlace[idx] = arr[i];
            ++idx;
            ++i;
        }else{
            outPlace[idx] = arr[j];
            ++idx;
            ++j;
        }
    }
 
    if(i > mid){
        while(j <= right){
            outPlace[idx] = arr[j];
            ++idx;
            ++j;
        }
    }else{
        while(i <= mid){
            outPlace[idx] = arr[i];
            ++idx;
            ++i;
        }
    }
 
    idx = left;
    while(idx <= right){
        arr[idx] = outPlace[idx];
        ++idx;
    }
}
 
void mergeSort(int arr[], int left, int right){
    if(left < right){
        int mid = (left + right) / 2;
 
        mergeSort(arr, left, mid);
        mergeSort(arr, mid+1, right);
        merge(arr, left, mid, right);
    }
}

• 머지 소트는 분할 정복 방식의 O(n logn) 속도를 지닌 빠른 정렬 기법이다.
• 퀵정렬에 비해 다소 느리지만, 퀵정렬과 다르게 항상 n log n 의 시간복잡도를 지니는 장점이 있다.
• merge 함수는 n 시간이 소요되며, 이때 새로운 배열에 기존 요소들을 정렬하며 담고, 마지막에 원래 배열로 복사가 이루어진다.
• 따라서 시간 복잡도에 비해 메모리 지역성이 다소 떨어지고 추가 메모리 공간이 필요하다.
• mergeSort 함수는 배열을 계속해서 반으로 나누는 분할 과정이고 log n 시간이 소요된다.
• 앞 서 언급한대로 추가 배열이 필요하기 때문에 2n 만큼이지만 빅오 표기법상 O(n)이라 할 수 있다.
• 이를 응용하면, 외부 병합 정렬을 이용할 수 있다.
• out of place 기법이다. ( in place로도 할 수는 있다고 한다. )