병합 정렬 ( Merge sort )

병합 정렬

- 분할 정복(Divide & Conquer) 방법을 사용하는 알고리즘

- 알고리즘을 구현함에 있어서 추가적인 임시 배열이 필요 ( 다른 정렬 알고리즘보다 메모리를 더 잡아먹음 )

 

 

시간 복잡도

O(N * logN) 

 

 

퀵 정렬 vs 병합 정렬

• 퀵 정렬은 최악의 경우 O(N * logN) 을 보장하지 못함 ( 최악의 경우 => O(N^2) )
• 병합 정렬은 최악의 경우에도 O(N * logN)을 보장함
• 둘 다 O(N*logN)만큼 걸리더라도 보통 병합 정렬보다 퀵 정렬이 더 빠름

 

병합 정렬의 동작 원리

1.  분할 ( 가장 작은 단위까지 분할 )   :   하나의 list를 두 개의 균등한 크기로 분할
2.  정렬 ( 가장 작은 단위부터 정렬 )   :   분할된 부분 list를 정렬

          =>  위 1,2 과정을 정렬이 완료될 때까지 반복 ( 재귀호출 )

 

 

 

분할된 부분 list를 정렬병합하는 과정

 

       (1) 각 요소의 첫번째 원소끼리 비교 시작

       

 

       (2) 비교한 후 작은 수를 임시 배열에 넣고 i++

 

 

 

       (3) 어느 한 쪽이 범위를 넘어가면 멈추고 남은 list의 값들을 뒤에 그대로 집어넣는다(정렬이 되어 있으므로)

 

 

병합정렬 알고리즘 구현

#include<iostream>
using namespace std;

int arr[10] = {1,3,5,7,9,2,4,6,8,10};
int* arr2;

void merge(int start, int end){
  int mid = (start + end) / 2;

  int i = start;
  int j = mid + 1;
  int temp = start;

  while(i <= mid && j <= end){
    if(arr[i] <= arr[j]){
      arr2[temp++] = arr[i++];
    }else{
      arr2[temp++] = arr[j++];
    }
  }

  int remain_idx = i > mid ? j : i;
  while(temp <= end){
    arr2[temp++] = arr[remain_idx++];
  }

  for(int i = start; i <= end; i++){
    arr[i] = arr2[i];
  }
}

void mergeSort(int start, int end){
  int mid;
  if(start < end){
    mid = (start + end) / 2;
    mergeSort(start,mid);
    mergeSort(mid+1,end);
    merge(start,end);
  }
}

int main(){
  arr2 = new int[10];
  mergeSort(0,9);

  for(int i = 0;i < 10; i++){
    printf("%d ",arr[i]);
  }

  delete[] arr2;
}