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

0. 병합 정렬

병합 정렬은 O(NlogN)의 시간복잡도를 가진 정렬 알고리즘이다.

가장 일반적인 O(N^2)인 삽입, 선택, 버블 정렬보다 빠르며,

많이 쓰이는 퀵 소트보다 높은 안정성을 보여준다.

퀵 소트는 평균적으로 O(NlogN)이지만 최악의 경우 O(N^2)이기 때문이다.

(이 이유때문에 알고리즘 문제에선 절대 퀵소트를 써선 안된다...)

자세한 건, 퀵 소트를 찾아보면 이해가 될 것이다.

---

1. 알고리즘

1. n의 길이를 가진 배열을 절반(m) 크기의 배열로 쪼갠다.
2. 쪼개진 배열의 길이가 2가 될 때까지 1번을 반복한다.
3. 쪼개진 두 배열을 [그림 1]과 같이 정렬한다.
4. m 길이의 정렬된 배열을 통해 2 * m 길이의 배열도 정렬한다.
5. 2 * m이 n이 될때까지 4번을 반복한다.

그림 1

 

그림 2

---

2. 코드

---

3. 참고

https://www.youtube.com/watch?v=59fZkZO0Bo4