MergeSort (병합 정렬)

이번에는 병합 정렬에 대해 알아보겠습니다.

 

병합 정렬은 이전에 살펴봤던 Karatsuba algorithm 과 비슷하게, 데이터의 크기를 작게 쪼갠 후

합치면서 정렬하는 방식입니다.

 

Karatsuba algorithm이 궁금하신 분들은 아래 글 참고 부탁드립니다.

 

https://sol248.tistory.com/46

Karatsuba Algorithm

 

 

 

다음 사진은 병합 정렬의 작동 방식입니다. 

 

작동 방식 자체는 간단하죠?

 

그럼 이제 코드를 한번 살펴보겠습니다.

 

 

코드(재귀)

class TopDownMerge {
 public:
  void Sort(std::vector<int>& v) {
    aux.resize(v.size());

    SortHelper(v, 0, v.size() - 1);
  }

 private:
  void Merge(std::vector<int>& v, int lo, int mid, int hi) {  //쪼개진 배열을 합치기
    int i = lo;
    int j = mid + 1;

    if (v[mid] <= v[j]) return;

    for (int k = lo; k <= hi; k++) {
      aux[k] = v[k];
    }

    for (int k = lo; k <= hi; k++) {
      if (i > mid)
        v[k] = aux[j++];
      else if (j > hi)
        v[k] = aux[i++];
      else if (aux[j] < aux[i])
        v[k] = aux[j++];
      else
        v[k] = aux[i++];
    }
  }
  
  void SortHelper(std::vector<int>& v, int lo, int hi) {  //배열을 쪼개고 Merge 호출
    if (lo >= hi) return;

    int mid = lo + (hi - lo) / 2;

    SortHelper(v, lo, mid);
    SortHelper(v, mid + 1, hi);
    Merge(v, lo, mid, hi);
  }
  std::vector<int> aux;
};

 

재귀를 사용하면 간단하게 구현할 수 있습니다.

 

병합정렬은 재귀호출을 사용하지 않고도 구현할 수 있는데요, 재귀를 사용하지 않고 어떻게 구현해야 할까요??

 

코드(재귀 사용x)

class BottomupMerge {
 public:
  void Sort(std::vector<int>& v) {
    int N = v.size();
    aux.resize(N);

    for (int k = 1; k < N; k = k + k)
      for (int g = 0; g < N - k; g += k + k)
        Merge(v, g, g + k - 1, std::min(g + k + k - 1, N - 1));
  }

 private:
  void Merge(std::vector<int>& v, int lo, int mid, int hi) {
    int i = lo;
    int j = mid + 1;

    if (v[mid] <= v[j]) return;

    for (int k = lo; k <= hi; k++) aux[k] = v[k];

    for (int k = lo; k <= hi; k++) {
      if (i > hi)
        v[k] = aux[j++];
      else if (j > hi)
        v[k] = aux[i++];
      else if (aux[i] > aux[j])
        v[k] = aux[j++];
      else
        v[k] = aux[i++];
    }
  }

  std::vector<int> aux;
};

재귀를 사용하지 않으려면 Sort함수에서 반복문을 통해 합치는 작업을 진행해주면 되겠죠.

 

 

분석)

이제 병합 정렬을 분석해보겠습니다.

 

이전에 karatsuba algorithm에서도 보았듯, 문제를 작게 쪼갠다고 무조건 더 효율이 좋아지는 것은 아닙니다.

 

쪼개고 합치는데 필요한 시간들은 아깝지 않을 정도로 더 빠른 뭔가가 있어야 한다는 말입니다.

 

병합정렬은 합치는데 이점이 있습니다.

 

아래 그림과 설명을 보면 왜 합치는 데에 이점이 있는지 알 수 있을 것입니다. 

 

 

병합 정렬의 시간 복잡도)

-일반적인 경우

 

레벨의 개수는 log(n) + 1

각 레벨의 시간복잡도는 O(n) 입니다.

 

각 레벨의 문제의 개수 * 각 레벨의 문제의 크기 = n 이므로 각 레벨의 시간 복잡도를 O(n) 이라고 할 수 있는 것입니다.

 

시간복잡도를 계산할 때 상수는 무시하므로 

 

병합정렬 전체의 시간 복잡도는 O(nlog(n)) 으로 분석할 수 있습니다.

 

 

 

 

 

-최선의 경우 

최선의 경우는 이미 배열이 정렬되어 있는 경우입니다.

위의 두 가지 코드에서 공통으로 있는 조건문이 있습니다.

if( v[mid] <= v[j] ) return; 입니다.

 

이 조건문은 두 배열을 합칠 때 이미 정렬되어있으면 더이상 비교할 필요 없이 바로 끝내는 조건문입니다.

 

그렇다면, 정렬된 배열의 경우 숫자의 비교 없이 바로바로 끝나게 되므로 바로 위의 그림과 같은 결과가 나오게 됩니다.

 

그럼 이제 각 레벨의 시간 복잡도를 모두 더해주면 최선의 경우 병합정렬 전체의 시간 복잡도를 구할 수 있을 것입니다.

 

 

거듭제곱의 합의 성질을 이용하여 시간 복잡도를 구하는 과정입니다.

 

저는 최선의 경우 시간복잡도를 Theta(n) 이라고 구했지만

 

구현 방식에 따라 최선의 경우에도 Theta(nlog(n)) 이 될 수 있습니다. 

 

if( v[mid] <= v[j] ) return;  이 조건문의 유무에 따라 최선의 경우에도 시간복잡도가 달라질 수 있다는 점 이해하시면 좋을 것 같습니다.