Time and Space Complexity

시간 복잡도:

• 최선, 평균, 최악의 경우: O(n log n)
  • 배열은 약 log n번 반으로 나뉘며, 각 단계에서 병합을 위해 O(n)의 작업이 수행됩니다. 실행 시간은 입력 순서에 의존하지 않습니다.

공간 복잡도:

• O(n)
  • 제자리 정렬(in-place sorts)과 달리, 병합 정렬(Merge Sort)은 병합하는 동안 새로운 배열을 생성하므로 입력 크기에 비례하는 추가 메모리가 필요합니다.

요약:

• 병합 정렬은 빠르고 예측 가능합니다: 모든 경우에 O(n log n)입니다.
• 안정 정렬(stable)이므로, 동일한 요소들은 기존의 순서를 유지합니다.
• 단점은 병합을 위해 추가적인 O(n) 메모리를 사용한다는 점입니다.