개념

요소를 쪼갠 후, 다시 합병시키면서 정렬해나가는 방식으로, 쪼개는 방식은 퀵정렬과 유사함

기본 아이디어

1. 정렬할 리스트를 앞쪽 반, 뒤쪽 반으로 나눈다.
   • 앞쪽 반을 정렬한다. (병합 정렬로 재귀적으로 정렬)
   • 뒤쪽 반을 정렬한다. (병합 정렬로 재귀적으로 정렬)
   • 리스트의 길이가 1이면 그 자체가 정렬되어 있다.
2. 이 둘을 병합해서 하나의 정렬된 리스트를 만든다.
   • 오름차순으로 정렬된 두 리스트 A,B의 병합
     • A가 비어 있다면 B를, B가 비어있다면 A를 리턴
     • 그렇지 않다면, 맨 처음 원소를 비교하고 작은 쪽을 리스트에 넣는다.
     • 이 원소를 제거하고 재귀적으로 진행

<aside> 💡 이미 합병이 되는 두 리스트는 정렬이 되어있기 때문에 단순히

</aside>

시간복잡도

두 리스트 병합의 시간 복잡도

• 최적: 두 리스트가 서로 교차되는 부분이 없을 때 N/2 (한쪽 끝나면 나머지는 통째로 넣으면 됨)
• 최악: 두 리스트가 서로 모두 교차할 때 N

점화식

• $T(n) = 2T(n/2)+n$ ⇒ $T(n) = O(nlogn)$
• n/2개의 리스트 2개를 정렬하고, 이를 합치는데 n번 비교