병합 정렬(merge sort)은 분할 정복(divide and conquer)방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘이다. 시간 복잡도 평균값은 O(nlogn)이다.
병합 정렬 수행 방식
그림을 보면 최초에는 8개의 그룹으로 나눈다. 이 상태에서 2개씩 그룹을 합치며 오름차순 정렬한다. 이를 계속 반복하며 전체를 오름차순 정렬한다.
2개의 그룹을 병합하는 과정
투 포인터 개념을 사용하여 왼쪽, 오른쪽 그룹을 병합한다. 왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값을 결과 배열에 추가하고 포인터를 오른쪽으로 1칸 이동시킨다.
- Do it! 알고리즘 코딩테스트 자바 편
