합병 정렬 (Merge Sort)

• 분할 정복 (divide and conquer) 기법으로 만들어진 정렬 방법
• 시간 복잡도 : O(N * logN)
  퀵 정렬은 Pivot 값에 따라서 편향되게 분할할 가능성이 있다는 점에서
  최악의 경우 O(N2)의 시간 복잡도가 날 수 있지만,
  병합 정렬은 분할과정이기 때문에 원소의 배치와 상관없이 O(N * logN)을 보장

1. 분할(Divide) - 해결이 용이한 단계까지 문제를 분할해 나간다.
2. 정복(Conquer) - 해결이 용이한 수준까지 분할된 문제를 해결한다.
3. 결합(Combine) - 분할해서 해결한 결과를 결합하여 마무리한다.

방식

예시1

{ 6, 5, 3, 1, 8, 7, 2, 4 }를 병합정렬 하는 과정

예시2

<분할>
재귀함수를 통해 크기가 = 1 (left >= right)될 때까지 분할

<합병>

작은 단위부터 merge할 때, 오름차순에 맞게 자리를 찾아감

예제

(s5) 2751 수 정렬하기 2 (합병 정렬)