분할 통치) 합병 정렬 (Merge sort)

합병 정렬

힙 정렬과 같이 비교에 기초한 정렬이며 수행 시간은 O(n log n)

하지만, 우선순위 큐를 사용하지 않고 데이터를 순차적 방식으로 접근한다.

과정

1. 분할 : L을 n/2 사이즈의 L1, L2로 분할

2. 재귀 : L1, L2를 재귀적으로 정렬

3. 통치 : L1, L2을 단일 순서리스트로 합병

코드를 보면 눈에 확 들어온다

Alg mergeSort(L)

if(L.size > 1 )
	(L1, L2) <-- partition(L, n/2)
	mergeSort(L1)
	mergeSort(L2)
	L <-- merge(L1, L2)

return L

실제 트리 ADT를 이용하는 것은 아니지만, 분할 하는 과정을 나열하면 트리 모양처럼 나온다.

이 과정에서 높이가 log n이 되므로

==> 합병 정렬의 수행시간은 O(n log n)이 성립한다.