<aside> 💡 병합 정렬은 코딩 테스트의 정렬 관련 문제에서 자주 등장한다. 특히 2개의 그룹을 병합하는 원리를 꼭 숙지해야 한다.
</aside>
병합 정렬은 분할 정복 (divide and conquer) 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘이다. 병합 정렬의 시간 복잡도 평균값은 **O(nlogn)**이다. 다만
병합 정렬 수행 방식
집합은 setN으로 표시
최초에는 8개의 그룹으로 나눈다. 이 상태에서 2개씩 그룹을 합치며 오름차순으로 정렬을 수행한다.그 결과 [32,42], [24,60], [5,15], [45,90]이 된다.
이어서 2개씩 그룹을 합치며 오름차순 정렬을 수행한다. 그 결과 [24,32,42,60], [5,15,45,90]이 된다.
이런 방식으로 병합 정렬 과정을 거치면 [5,15,24,32,42,45,60,90]이 되어 전체를 오름차순 정렬할 수 있다.
투 포인터 개념을 사용해 왼쪽, 오른쪽 그룹을 병합한다. 왼쪽 포인터와 오른쪽 포인터의 값을 비교해 작은 값을 결과 배열에 추가하고 포인터를 오른쪽으로 1칸 이동시킨다.
<aside> 💡 마지막에 모두 넣어준 이유는 한 쪽 포인터가 끝까지 도달했기 때문에 반대쪽 포인터는 출력만 하면 된다.
</aside>
