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

현재 차근차근 해보자는 생각에 기초적인 부분을 공부하고 있다. 좀 더 구체적인 내용은 다른 글에 작성하거나 추후 글을 수정하는 방향으로 해보겠다.

틀린 내용이 있거나 궁금한게 있다면 편하게 댓글 남겨주시면 감사하겠습니다.

---

📌 개념

병합 정렬은 정렬할 수열을 거의 같은 길이의 수열 두 개로 분할한다. 더 이상 분할 할 수 없게 되면(즉, 각 그룹의 숫자가 한 개가 되면) 그룹끼리 통합하기 시작한다. 통합할 때는 정렬된 수열 두 개를 통합하여 하나로 정렬한다. 이러한 과정을 정렬된 수열이 하나가 될 때까지 반복한다.

 

병합 정렬

1부터 7까지의 임의의 수열로 예를 들어 보겠다.

먼저 수열을 반으로 분할해 간다.

 

병합 정렬

먼저 두개로 분할 하고...

 

병합 정렬

다시 분할하여..

 

병합 정렬

하나씩 될 때 까지 분할해 준다. 이제 분할이 완료되었으니 그룹을 합체 해준다.

 

병합 정렬

2와 7을 합쳐 [2, 7]로 정렬 된다.

 

병합 정렬

4와 5를 합쳐 [4, 5]로 정렬된다.

 

병합 정렬

이제 [4, 6]과 [3, 7]을 합쳐보겠다.

이 처럼 둘 이상의 숫자를 포함한 그룹을 통합할 때는 앞에 있는 숫자를 비교하여 작은 쪽의 숫자를 이동한다.

 

병합 정렬

2 < 4이기 때문에 2를 이동한다.

마찬가지로 두 그룹에 남은 숫자 중 앞에 있는 두 수를 비교하여...

 

병합 정렬

4 < 7이기 때문에 4를 이동한다.

 

병합정렬

이제 남은 7과 5를 비교하면

병합 정렬

5 < 7이기 때문에 5를 이동한다.

 

병합 정렬

이제 남은 7까지 이동 시켜주면 통합이 완료된다.

 

병합 정렬

그룹 간 통합은 모든 수가 하나의 그룹이 될 때 까지 재귀적으로 진행한다.

 

병합 정렬

 

여기서도 계속해서 맨 앞의 두 수를 비교한다.

 

병합 정렬

 

1 < 2 이기 때문에 1을 이동 시킨다. 이를 계속하면..

 

병합 정렬

합체가 완료되고 모든 수가 정렬이 된다.

---

 

⏱️ 시간복잡도

병합 정렬에서 숫자를 분할하는 작업의 계산 시간은 없다. (처음부터 분할되어 있다고 생각해도 된다.)

정렬된 두 수열을 병합하는 부분은 앞에 있는 수를 비교하여 작은 숫자를 위로 옮기는 작업을 반복하기 때문에 두 수열의 길이에 비례한다. 따라서 하나의 층을 병합하는 계산 시간은 그 층에 있는 숫자의 수를 따른다.

 

위 예시를 보면 알겠지만, 어던 층을 봐도 숫자는 n개이므로 각 층의 계산 시간은 O(n)이다. n개 숫자가 하나가 될 때까지 절반식 분할해 나가면 log₂n층이므로 전체 계산 시간은 O(n log n)입니다.

 

---

참고 자료

그림으로 이해하는 알고리즘 : 이시다 모리테루, 미야자키 슈이츠