머지 소트

퀵소트와 마찬가지로 O(nlogn)의 시간 복잡도를 가진 친구

하지만 In-place update로 구현할 경우 같은 공간 내에서 교환을 해야하기 때문에

더 많은 시간적 비용이 소모된다.

 

따라서 임시 배열을 동적 할당해주거나

아니면 정렬하고자 하는 배열과 같은 크기의 임시 배열을 선언해

out-place update로 시행한다