병합 정렬은 효율적인 정렬 알고리즘 중 하나로, 분할 정복(Divide and Conquer) 방식을 사용하는 것이 특징이다.
병합 정렬은 다음과 같은 세 단계로 동작한다.
: 정렬할 리스트를 두 개의 균등한 크기(또는 거의 균등한)의 서브 리스트로 분할한다.
이 과정은 서브 리스트의 크기가 1이 될때까지 재귀적으로 반복된다.
크기가 1인 리스트는 이미 정렬되었다고 간주한다.
: 분할된 서브 리스트들을 각각 재귀적으로 정렬한다.
: 정렬된 두 개의 서브 리스트를 다시 하나의 정렬된 리스트로 병합한다.
이 병합 과정이 병합 정렬의 핵심이다.