[알고리즘] Merge sort 병합 정렬

• 병합 정렬
  주어진 배열을 더 이상 쪼갤 수 없을 때까지 데이터 크기의 절반으로 계속 나누어, 재귀적으로 정렬을 수행하면서 통합하는 정렬 알고리즘
  이 알고리즘 총 3단계로 나눌 수 있다.

1. Divide
   주어진 배열을 데이터 크기의 절반으로 나누어 2개의 부분 배열로 분할한다.
   이를 더 이상 쪼갤 수 없을 때까지 분할한다.
2. Conquer
   나누어진 부분 배열에 대해서 재귀적으로 합병 정렬을 한다.
3. Combine
   정렬한 2개의 부분 배열을 통합하여 원래 크기의 정렬된 배열로 만든다.

---

• Merge sort의 슈도 코드

 

• Merge sort의 수행 과정

• Merge sort의 시간 복잡도
  먼저 전체 리스트를 반으로 나누어 가면서 리스트를 분할한다. 만약 길이가 8인 리스트라면 이를 총 3번 나눌 것이고, 길이가 16인 리스트는 총 4번 나누어 분리와 병합을 진행할 것이다. 즉, 2의 제곱수 형태로 리스트를 나누는 횟수가 증가하는 것을 알 수 있다.
  정렬하고자 하는 리스트의 길이가 n이라면 log n번 나누는 것을 알 수 있다. 이는 원소의 개수마다 분리와 병합이 나타나므로 n번의 연산이 필요하다. 따라서 최종적으로 시간 복잡도는 O(nlog n)인 것을 알 수 있습니다.
• Merge sort의 적용
  합병(병합) 정렬은 외부 정렬의 기본이 되는 정렬 알고리즘이다. 리스트에 있는 데이터를 정렬할 때에도 퀵 저열이나 힙 정렬보다 훨씬 효율적이다. 멀티코어 CPU와 다수의 프로세서로 구성된 그래픽 처리 장치의 등장으로 정렬 알고리즘을 병렬화하는 데에 합병 정렬 알고리즘이 활용된다.