정렬 알고리즘 - 병합 정렬(Merge Sort)

병합 정렬(Merge Sort)

 

• 고급 정렬 알고리즘(병합 정렬, 퀵 정렬, 힙 정렬) 중 하나
  
  
• 고급 정렬 알고리즘 분석
• 평균적으로 Θ(nlogn)의 시간이 소요되는 정렬 알고리즘들
• 병합 정렬(합병 정렬)
• 퀵 정렬
• 힙 정렬
  
  
• 최악의 경우
• 병합 정렬과 힙 정렬 → Θ(nlogn)
• 퀵 정렬 → Θ(n²)
  
  
• 수행 방법
• 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방법
• 부분 집합으로 분할(divide)하고, 각 부분집합에 대해서 정렬 작업을 완성(conquer)한 후에 정렬된 부분집합들을 다시 결합(combine)하는 분할 정복(divide and conquer)기법 사용
  
  
• 병합 정렬 방법의 종류
• 2-way 병합 : 2개의 정렬된 자료의 집합을 결합하여 하나의 집합으로 만드는 병합 방법
• n-way 병합 : n개의 정렬된 자료의 집합을 결합하여 하나의 집합으로 만드는 병합 방법
  
  
• 2-way 병합 정렬 : 세 가지 기본 작업을 반복 수행하면서 완성
  1. 분할(divide) : 입력 자료를 같은 크기의 부분집합 2개로 분할 한다.
  2. 정복(conquer) : 부분집합의 원소들을 정렬 한다.
  3. 결합(combine) : 정렬된 부분 집합들을 하나의 집합으로 통합 한다.
  
  
  
• 병합 정렬 수행 과정
• 정렬 되지 않은 [69, 10, 30, 2, 16, 8, 31, 22]의 자료들을 병합 정렬 방법으로 정렬하는 과정을 살펴보자.
  
  1. 분할 단계 : 정렬할 전체 자료의 집합에 대해서 최소 원소의 부분집합이 될때까지 분할 작업을 반복하여 1개의 원소를 가진 부분집합 8개를 만든다.   

                     2. 병합 단계 : 2개의 부분집합을 정렬하면서 하나의 집합으로 병합한다. 8개의 부분집합이 1개로 병합될 때까지 반복한다.

 

 

• 병합 정렬 알고리즘