정의

병합 정렬(Merge Sort)은 배열을 계속 반으로 나누고, 나눠진 작은 배열들을 정렬한 뒤, 다시 합쳐서 전체를 정렬하는 알고리즘입니다. 마치 카드를 여러 뭉치로 나눠서 각각 정리한 뒤, 다시 순서대로 합치는 것과 같습니다.

핵심 특성

• ✓분할 정복 (Divide and Conquer) - 큰 문제를 작게 나눠서 해결
• ✓항상 O(n log n) 보장 - 최악의 경우에도 빠름
• ✓안정 정렬 - 같은 값의 순서가 바뀌지 않음
• ✓추가 메모리 필요 O(n) - 임시 배열을 사용

시간 복잡도