merge sort (1) 썸네일형 리스트형 31. Merge Sort 이번에는 $\Theta(n^2)$보다 빠른 시간복잡도를 갖는 정렬 방법을 알아보자. 그중 가장 간단하다고 할 수 있는 병합 정렬(합병 정렬, Merge Sort)은 데이터를 여러 구간으로 분할한 후 각각의 구간을 정렬한 후 합치는 방법으로 데이터를 정렬한다. 분할 정복을 이용한 정렬 방법으로 볼 수도 있다. (사실 시간복잡도가 $\Theta(n\text{ lg }n)$인 정렬 알고리즘들 대부분이 분할 정복을 기반으로 하지만 병합 정렬에서 그 특징이 가장 두드러진다고 할 수 있다.) 다음은 병합 정렬 과정을 시뮬레이션한 것이다. 그림으로 도식화하면 다음과 같다. 시뮬레이션에서도 알 수 있듯이 원소 $n$개의 정렬과 병합을 $\Theta(n)$ 시간에 수행할 수 있기 때문에 시간복잡도가 $\Theta(n\t.. 이전 1 다음
