• 분할 정복(divide and conquer) 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘
• 시간 복잡도는 O(nlogn)

2개의 그룹을 병합하는 과정

• 투 포인터 개념을 사용하여 왼쪽, 오른쪽 그룹을 병합
• 왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값을 결과 배열에 추가하고 포인터를 오른쪽으로 1칸 이동

[020] 수 정렬하기 2

• https://www.acmicpc.net/problem/2751
• 병합 정렬 사용해서 풀기

[021] 버블 소트 프로그램 2

• https://www.acmicpc.net/problem/1517
• 버블 정렬이 아닌 O(nlogn)의 시간 복잡도를 가진 병합 정렬을 사용해야함
• 두 그룹을 병합하는 과정에 버블 정렬의 swap이 포함되어 있음