병합 정렬은 작은 부분들을 정렬한 뒤 두 정렬된 결과를 병합하는 분할 정복 정렬이다.
원리
두 부분의 앞 원소를 비교하며 더 작은 것을 결과로 옮긴다. 균등하게 나누는 일반적인 구현의 시간 복잡도는 O(n log n)이다.
예시
정렬된 1, 4와 2, 3을 병합하면 앞 원소를 차례로 비교해 1, 2, 3, 4를 얻는다. 같은 키에서는 왼쪽을 먼저 선택하면 안정성을 유지할 수 있다.
주의할 점
배열 구현은 일반적으로 O(n) 보조 공간을 사용한다. 연결 리스트 구현이나 외부 정렬에서는 저장과 병합 방식이 달라질 수 있다.