31. Merge Sort

이번에는 $\Theta(n^2)$보다 빠른 시간복잡도를 갖는 정렬 방법을 알아보자. 그중 가장 간단하다고 할 수 있는 병합 정렬(합병 정렬, Merge Sort)은 데이터를 여러 구간으로 분할한 후 각각의 구간을 정렬한 후 합치는 방법으로 데이터를 정렬한다. 분할 정복을 이용한 정렬 방법으로 볼 수도 있다. (사실 시간복잡도가 $\Theta(n\text{ lg }n)$인 정렬 알고리즘들 대부분이 분할 정복을 기반으로 하지만 병합 정렬에서 그 특징이 가장 두드러진다고 할 수 있다.)

 

다음은 병합 정렬 과정을 시뮬레이션한 것이다.

그림으로 도식화하면 다음과 같다.

시뮬레이션에서도 알 수 있듯이 원소 $n$개의 정렬과 병합을 $\Theta(n)$ 시간에 수행할 수 있기 때문에 시간복잡도가 $\Theta(n\text{ lg }n)$이 된다. 하지만 공간복잡도도 $\Theta(n \lg n)$으로, 분할된 배열과 병합된 배열을 저장할 메모리가 많이 필요해서 다른 정렬 알고리즘에 비해 공간복잡도가 크다는 단점이 있다.

 

→ solved.ac tag: sorting