[알고리즘]병합정렬

병합정렬

정렬 할 배열을 반복하여 최대한 작게 쪼갠 후 인접한 원소끼리 정렬하며 병합하는 방식이다. 병합정렬의 시간 복잡도 평균값은 O(nlogn)이다. 과정을 그림으로 보면 다음과 같다.

병합 정렬은 코딩 테스트의 정렬 관련 문제에서 자주 등장한다. 특히 2개 그룹을 병합하는 원리는 꼭 숙지해야 한다. 2개의 그룹을 병합하는 원리는 다음과 같다.투포인터 개념을 이용해 두 그룹을 병합한다. 왼쪽과 오른쪽 포인터 값을 비교하여 작은 값을 결과 배열에 추가하고 포인터를 오린쪽으로 1칸 이동시킨다.