[알고리즘] Merge Sort

Abstract

• Merge Sort는 분할 정복(Divide and Conquer) 방법을 통해 주어진 배열을 정렬한다.

Divide and Conquer
문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략

Process(Ascending)

1. 영역을 두개의 sub problem으로 쪼갠다. 이때, 쪼갠 영역의 크기는 최대한 같게 한다. ➡ MergeSort
2. 쪼갠 영역을 합병하면서 정렬한다. ➡ Merge

C++ Code(Ascending)

MergeSort

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);
  }
}

Merge

void merge(int arr[], int left, int mid, int right){
  int ll = mid-left+1; // left array length
  int rl = right-mid; // right array length
  int L[ll], R[rl];

  for(int i=0; i<ll; i++){
    L[i] = arr[left+i];
  } 
  for(int j=0; j<rl; j++){
    R[j] = arr[mid+1+j];
  }

  int i=0, j=0, k=left;
  while(i<ll && j<rl){
    if(L[i] <= R[j]){
      arr[k] = L[i++];
    }
    else{
      arr[k] = R[j++];
    }
    k++;
  }

  while(i<ll){
    arr[k++] = L[i++];
  }
  while(j<rl){
    arr[k++] = R[j++];
  }
}

GIF로 이해하는 Merge Sort

시간복잡도

• 비교횟수 : log₂n
  레코드의 개수 n이 2의 거듭제곱이라고 가정했을 때, n = 2^k라고 표현할 수 있다.
  n = 2^3의 경우, 2^3 -> 2^2 -> 2^1 -> 2^0 순으로 줄어들어 순환 호출의 깊이가 3이다.
  이를 일반화 하면, n = 2^k 이므로 호출의 깊이는 k이다.
  이 때, k = log₂n 이므로 비교횟수는 log₂n 이다.

• 각 순환 호출 단계의 비교 연산 : n
  각 순환 호출에서 전체 리스트의 거의 모든 레코드를 비교해야 하므로 n번의 비교가 발생한다.

따라서 시간복잡도는 순환 호출의 깊이 * 각 순환 호출 단계 비교 연산 = nlog₂n가 된다.

Best case : O(nlog₂n)
Worst case : O(nlog₂n)
Average case : O(nlog₂n)

공간복잡도

O(n)

장점

• 안정 정렬
• 빠르다

단점

• 제자리 정렬을 하지 않고 새로운 메모리에 정렬 후에 원래 리스트에 결과를 저장한다.
• 실제 사용시 퀵 소트와 힙 소트보다 느린 경우가 많다.

참고 사이트

Merge Sort1
Merge Sort2
Merge Sort3