📘[Algorithms] 병합정렬(Merge_Sort)에 대해서

병합정렬(Merge_Sort)란

병합정렬은 분할정복(Divide and Conquer)방식을 이용한 정렬 알고리즘이다.
병합정렬은 안정정렬에 속한다.

병합정복 과정

1. 리스트의 길이가 0 혹은 1이면 이미 정렬된 것으로 판단
2. 정렬되지 않은 리스트를 절반으로 잘라 두 개의 부분 리스트로 나눔 (분할)
3. 각 부분 리스트를 재귀 방식으로 병합정렬을 이용해 정렬 (정복)
4. 두 부분 리스트를 다시 결합시킴 (결합)

예시

병합정렬의 시간복잡도

병합정렬의 시간 복잡도는 n개의 데이터를 logN 단계를 거쳐 진행하기 때문에 O(NlogN)의 시간복잡도를 갖는다.