병합 정렬 (Merge Sort) 비교 기반 정렬 알고리즘 분할 정복(Divide And Conquer) 알고리즘의 하나 분할 정복 (Divide And Conquer) 큰 문제를 작은 문제로 나눠서(분할하여) 해결하는(정복하는) 방법 입력 크기가 큰 문제도 작게 나누는 것을 반복하면 쉬운 문제, 즉 종료 조건이 되는 원리 이용 정렬 방법 리스트의 길이가 0 또는 1이면 정렬된 상태로 판단한다. 리스트가 정렬되지 않았으면, 반으로 나눠 부분 리스트를 생성한다. 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다. 정렬된 리스트를 하나의 리스트로 병합한다. 계산 복잡도는 $$ O(n\log{n}) $$ 코드 def merge_sort(list): n = len(list) # 종료 조건 if n