Day-7 병합 정렬

---

1. 병합 정렬

• 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 합치며 정렬하는 방식이다.
• 평균 시간 복잡도는 O(nlogn)이다.

---

2. 병합 정렬 과정

 

최초에는 8개의 집합으로 나눈다.

2개씩 집합을 합치며 오름차순 정렬한다.

(42)와 (32)가 합쳐져 (32, 42)로 정렬된다.

이와 같은 과정을 집합이 하나가 될 때까지 반복하면 된다.

---

3. 그룹 병합 과정

 

자세한 병합 과정은 위 그림과 같다.

(24, 32, 42, 60)과 (5, 15, 45, 90) 두 집합을 병합하는 과정이다.

집합의 최소값을 가리키는 포인터를 각각 생성한다.

포인터가 가리키는 값을 비교하여 더 작은 값을 결과 배열에 추가한다.

---

4. 예제 문제

[2751] 수 정렬하기 2 (JAVA)

---

[24060] 알고리즘 수업 - 병합 정렬 1 (JAVA)