해당 포스트는 이지스퍼블리싱, 『알고리즘 코딩테스트 자바 편』, Gene 김종관 을 참고하여 작성하였습니다.

병합 정렬(merge sort)은 분할 정복(divide and conquer)방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘입니다. 병합 정렬의 시간 복잡도 평균은 O(nlogn)입니다.

병합 정렬의 핵심 이론

• 가장 작은 데이터 집합으로 분할
• 병합하면서 정렬

병합 정렬 수행 방식

| 42 | 32 | 24 | 60 | 15 | 5 | 90 | 45 |

예를 들어 최초에는 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)이 되어 전체를 오름차순으로 정렬할 수 있습니다.

병합 정렬은 코딩 테스트의 정렬 관련 문제에서 자주 등장합니다. 특히 2개의 그룹을 병합하는 원리는 꼭 숙지해야 합니다!

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

투 포인터 개념을 사용하여 왼쪽, 오른쪽 그룹을 병합합니다. 왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값을 결과 배열에 추가하고 포인터를 오른쪽으로 1칸 이동시킵니다. 이 방식은 여러 문제에서 응용하므로 반드시 숙지하는 것이 좋습니다!

[참고자료] https://yujuwon.tistory.com/entry/%EB%B3%91%ED%95%A9%EC%A0%95%EB%A0%ACMerge-Sort