[알고리즘] 병합 정렬

학습 목표

재귀를 활용한 병합 정렬을 구현할 수 있다.

1. 정렬 알고리즘

• 대표적인 정렬방법 중 하나이다.
• 전화번호부에서 mike를 찾기 위해 절반을 나눠서 탐색해나갔던 분할 정복 탐색처럼 데이터를 반으로 나누어간다는 공통점이 있다.
• 병합 정렬은 원소가 한 개가 될 때까지 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식이다.

2. 예시

임의로 나열된 8개의 숫자를 오름차순으로 정렬해보자.

7 4 5 2 6 3 8 1

• 먼저 숫자를 반으로 나누자.
• 7 4 5 2 | 6 3 8 1
• 나눠 놓은 덩어리를 한번 더 나눠보자.
• 7 4 | 5 2 | 6 3 8 1
• 또 나누자.
• 7 | 4 | 5 2 | 6 3 8 1
• 원소가 한 개가 남았으므로 더 이상 나눌 수가 없다. 두 숫자를 작은 숫자가 먼저 오도록 병합하자.
• 4 7 | 5 2 | 6 3 8 1
• 5 2 부분도 같은 방법으로 병합하자.
• 4 7 | 2 5 | 6 3 8 1
• 4 7 과 2 5 부분도 병합하자. 앞에서부터 순서대로 읽어서 비교하고 더 작은 숫자를 가져오자.
  2와 4를 비교해서 2를 가져오고, 그 후에 4와 5를 비교해서 4를 가져오고, 그 후에 7과 5를 비교해서 5를 가져오고, 남아 있는 7을 가져온다.
• 2 4 5 7 | 6 3 8 1
• 오른쪽 4개 숫자들도 동일한 작업을 반복하자.
• 2 4 5 7 | 1 3 6 8
• 마찬가지로 1과 2를 비교해서 1을 가져오고, 그 후에 2와 3을 비교해서 2를 가져온다. 그 후에 4와 3을 비교해서 3을 가져오고, 4와 6을 비교 후 4를 가져오고, 5와 6 비교 후 5를 가져오고...
• 1 2 3 4 5 6 7 8