Motivation

병합 정렬(Merge Sort)은 문제를 더 작은 하위 문제로 나누고, 각각을 해결한 다음, 그 결과를 결합합니다. 이미 정렬된 두 리스트를 합치는 이 결합 단계가 알고리즘의 핵심입니다.

왜 병합 정렬을 배워야 할까요?

• 빠르고 예측 가능함: 최선, 평균, 최악의 경우 모두 O(n log n) 시간에 실행됩니다.
• 안정성(Stable): 동일한 요소들이 원래의 상대적인 순서를 유지합니다.
• 대용량 데이터에 적합: 데이터가 메모리에 다 들어가지 않는 경우(외부 정렬)와 연결 리스트(linked lists)에 잘 작동합니다.
• 분할 정복(Divide and conquer): 많은 고급 알고리즘에서 사용되는 패턴을 가르쳐 줍니다.