병합 정렬의 핵심 이론
병합 정렬(merge sort)은 분할 정복(divide and conquer)방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘이다. 병합 정렬의 시간 복잡도는 O(nlogn)이다.
수행 방식
부분 그룹은 setN으로 표시했다.
그림을 보면 최초에는 8개의 그룹으로 나뉜다. 이 상태에서 2개씩 그룹을 합치며 오름차순 정렬한다. 이런 방식으로 병합 정렬 과정을 거치면 전체를 오름차순으로 정렬할 수 있다.
병합 정렬은 코딩 테스트의 정렬 관련 문제에 자주 등장한다. 특히 2개의 그룹을 병합하는 원리는 꼭 숙지해야 한다.
2개의 그룹을 병합하는 과정
투 포인터 개념을 사용하여 왼쪽, 오른쪽 그룹을 병합한다. 왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값을 결과 배열에 추가하고 포인터를 오른쪽으로 1칸 이동시킨다. 이 방식은 여러 문제에서 응용하므로 반드시 숙지하는 것이 좋다.
