알고리즘 개념[기초] - 병합 정렬

병합정렬은 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘 입니다.

시간 복잡도 : O(nlogn)

핵심이론은 처음 가장 작은 데이터 집합으로 분할합니다. 그 다음 병합하면서 정렬을 하며, 마지막에는 큰 집합 2개를 병합하여 정렬을 하게 됩니다. 이 때, 2개의 그룹을 병합하는 원리는 다음과 같습니다.

1. 투포인터를 지정 및 왼쪽 그룹과 오른쪽 그룹을 비교하여 작은 값을 결과 배열에 추가하고 포인터를 오른쪽으로 1칸 이동시킵니다.
2. 위 과정을 반복하여 모든 값이 정렬된 경우 즉, 결과 배열이 마지막 배열인 경우 투 포인터가 가리키는 값을 비교하여 차례로 넣어준 뒤 정렬을 종료합니다.