병합정렬

분할정복의 대표적인 예

merge : 정복, sort : 분할, 2개의 함수로 구성되어 있다

 

1. stable sort 중 하나로 중복 키 순서가 보장된다 

2. 평균, 최악, 최고의 시간복잡도는 동일하게 O(NlgN)이다

3. 임시로 저장해야하는 배열이 있어야하므로 기존보다 2배의 메모리를 잡아먹는다

 

위 채점은 merge sort로 아래 채점은 heap sort이다

 

깃허브주소: https://github.com/surinoel/boj/blob/master/merge_sort.cpp