병합 정렬

요소가 2개 이상인 경우, 

1. 앞 부분을 병합 정렬한다.

2. 뒷 부분을 병합 정렬한다.

3. 앞 부분과 뒷 부분을 병합한다.

 

추가 공간을 필요로 하기 때문에 제자리 정렬이 아니다.

안정적이다.

 

이진트리로 대입해서 생각해보면,

이진트리의 높이, 즉, 반으로 나눗 횟수, 다시 병합할 횟수, stage 수 등등 -> logN

어느 한 레벨에서 노드 2^M개, 한 노드에 있는 요소수 N*(1/2)^M개이므로 한 레벨에서

비교에 대한 복잡도는 O(2^M * N*(1/2)^M) -> O(N)이다.

따라서 O(NlogN)의 시간복잡도를 가진다.