병합 정렬 (1) 썸네일형 리스트형 [알고리즘] 정렬(2) - 병합 정렬, 퀵 정렬, 힙 정렬 앞에서는 시간 복잡도가 \(\Theta(n^2)\)인 정렬 알고리즘들을 알아봤다. 이번에는 \(\Theta(nlogn)\)인 알고리즘들을 알아보자. 병합 정렬(Merge Sort) 병합 정렬은 먼저 입력을 절반으로 나눈다. 이후 그 두 덩이를 각각 정렬한 뒤, 서로 합쳐서 정렬하는 방식이다. 나뉘어진 두 덩어리도 다시 반으로 나눈 뒤 정렬하고 병합하고, 또 그 나누어진 덩이를 나누는 과정을 반복한다. 즉, 정렬 과정을 재귀적으로 반복하는 방법이다. 3 2 4 1 우선 절반을 가른다. 3 2 4 1 각각을 또 절반으로 가른다. 3 2 4 1 왼쪽과 오른쪽에서 자른 덩어리를 합하며 정렬한다. 2 3 1 4 나머지 덩어리를 합하며 정렬한다. 1 2 3 4 정렬이 끝난 배열 1 2 3 4 C++로 구현한 병합정.. 이전 1 다음