[CS50] 4.8 병합 정렬
병합 정렬이란 전화번호부를 반씩 나누어 간다는 것과 비슷하다.
원소가 한 개가 될 때까지 계속 반으로 나누다가 다시 합쳐나가며 정렬하는 방식이다.
<병합 정렬하는 방법>
①최소 단위로 나눈 다음,
②나눈 곳 기준 왼쪽을 정렬한다.
③나눈 곳 기준 오른쪽을 정렬한다.
④위에서 정렬한 것을 병합한 후 오름차순으로 정렬한다.
이 과정을 계속 반복한다.
예시)
7 | 4 | 5 | 2 | 6 | 3 | 8 | 1 → 가장 작은 부분(숫자 1개)으로 나눈다.
4 7 | 2 5 | 3 6 | 1 8 → 숫자 1개씩을 정렬하여 병합한다.
2 4 5 7 | 1 3 6 8 → 숫자 2개씩을 정렬하여 병합한다.
1 2 3 4 5 6 7 8 → 마지막으로 숫자 4개씩을 정렬하여 병합한다.
알고리즘에서 무언가를 계속 절반으로 나눈다면 이것은 로그 함수로 표현할 수 있다.
병합정렬에서는 나누는 과정이 있을 때마다 합치는 과정이 있다.
따라서 모든 n개의 항목을 확인하게 된다.
높이는 log n이 된다. 나눌 수 있는 횟수가 log n번이기 때문이다.
병합 정렬 실행 시간의 상한은 O(n log n)이다.
n개의 숫자를 다시 합쳐야 하고 log n번을 나눠야(반복) 하기 때문이다.
숫자들을 반으로 나누는 데는 O(log n)의 시간이 들고,
각 반으로 나눈 부분들을 다시 정렬해서 병합하는 데 각각 O(n)의 시간이 걸리기 때문이다.
병합 정렬 실행 시간의 하한도 Ω(n log n)이다.
병합정렬은 버블정렬처럼 교환이 일어나지 않을 때 멈출 수 있는 최적화 기법이 없어서
이미 정렬되어 있어도 정렬을 수행한다.