[알고리즘/정렬] Merge Sort 합병 정렬 - C++ 코드, 시간/공간 복잡도

알고리즘에 대한 설명은 많은 곳에 있으니 생략하고, 코드와 시간복잡도 및 공간복잡도만 살펴보겠다.

void mergeSort(vector<int>& v, int s, int e) {
    if(s >= e) return;

    int m = (s+e)/2;

    // divide
    mergeSort(v, s, m); // s ~ m
    mergeSort(v, m+1, e); // m+1 ~ e

    // conquer
    vector<int> ret(e+1);
    int ret_idx = 0;
    int i = s, j = m+1; // i : s ~ m, j : m+1 ~ e

    // 결과를 저장할 배열에 하나씩 비교하여 저장
    while(i <= m && j <= e) {
        if(v[i] < v[j]) ret[ret_idx++] = v[i++];
        else ret[ret_idx++] = v[j++];
    }

    // 남은 값들을 뒤에 채워넣어준다
    while(i <= m) ret[ret_idx++] = v[i++];
    while(j <= e) ret[ret_idx++] = v[j++];

    // 원래 배열에 복사
    for(int k = s, ret_idx = 0 ; k <= e ; k++, ret_idx++) 
        v[k] = ret[ret_idx];
}

C++로 작성된 코드이다.

분할과 합병하는 부분을 분리하지 않고 하나의 함수로 하도록 표현하면 저렇게 된다.

분리하여 함수 2개를 사용하는 코드는 아래와 같다

void mergeSort(vector<int>& v, int s, int e) {
    if(s >= e) return;

    int m = (s+e)/2;

    // divide
    mergeSort(v, s, m); // s ~ m
    mergeSort(v, m+1, e); // m+1 ~ e

        // conquer
        merge(v, s, e, m);
}

void merge(vector<int>& v, int s, int e, int m) {
    vector<int> ret(e+1);
    int ret_idx = 0;
    int i = s, j = m+1; // i : s ~ m, j : m+1 ~ e

    // 결과를 저장할 배열에 하나씩 비교하여 저장
    while(i <= m && j <= e) {
        if(v[i] < v[j]) ret[ret_idx++] = v[i++];
        else ret[ret_idx++] = v[j++];
    }

    // 남은 값들을 뒤에 채워넣어준다
    while(i <= m) ret[ret_idx++] = v[i++];
    while(j <= e) ret[ret_idx++] = v[j++];

    // 원래 배열에 복사
    for(int k = s, ret_idx = 0 ; k <= e ; k++, ret_idx++) 
        v[k] = ret[ret_idx];
}

 

 

시간 복잡도 : 모든 경우에서 NlogN

BEST	AVG	WORST
NlogN	NlogN	NlogN

배열이 어떻게 구성되어 있더라도 신경쓰지 않고 분할하기 때문에 시간 복잡도는 항상 같다.

 

공간 복잡도 : O(N)

매번 ret이라는 배열을 생성하는 것을 알 수 있다. 이렇게 병합 과정에서 임시로 저장해둘 배열을 사용하기 때문에 공간복잡도는 O(N) 이다.