이전 포스팅에서 살펴본 정렬 알고리즘들은 평균, 최악의 경우 $O(n^2)$의 시간복잡도를 가지게 되었다.  병합 정렬 (Merage Sort)"병합 정렬"(또는 합병 정렬)은 문제를 분할하고, 문제를 정복하여 합치는 분할정복을 기반으로 한 정렬 알고리즘이다.   정렬 과정이러한 분할정복은 "하향식"과 "상향식"구현으로 구분할 수 있는데,병합 정렬에선 하향식 구현방식을 대부분 사용한다. 하향식(TopDown)방식으로 구현한 병합 정렬의 과정은 다음과 같다. (아래 그림은 정확한 Top-Down 방식은 아니지만, 분할되고 정복되는 순서만 차이 있을 뿐, 방법은 동일하다.)리스트를 절반으로 나누어 두 부분 리스트로 나눈다. 이를 부분 리스트의 길이가 1이하가 될 때까지 재귀적으로 위의 과정을 반복한다. (길..