힙을 사용한 정렬. 힙에 데이터를 다 넣고 빼는게 다다.
정렬을 할경우 정렬대상의 수 만큼 삽입 및 삭제해야하므로 위의 빅-오에 n 을 곱해야 한다.
O(nlog2n)
이번에 소개하는 병합 정렬은 ‘분할 정복(divide and conquer)’이라는 아고리즘 디자인 기법에 근거하여 만들어진 정렬 방법이다. 단 분할해서 정복했으니 정복한 후에는 ‘결합(combine)’의 과정을 거쳐야한다.
사이즈가 1 이 될때까지 쪼갠후 다시 병합하며 정복한다.
O(nlogn): n 번의 비교와 logn 만큼의 높이를 가지기 때문.
임의의 pivot 을 정하고 left right 을 한칸씩 반대쪽으로 옮기면서 pivot 보다 크거나 작은 숫자에 둘다 도달했을때 swap 을 한후 마지막에 high 와 swap 하여 왼쪽에는 작은 숫자 오른쪽은 큰숫자만 있게한다.
O(nlogn) 빅오는 O(n^2) 맞긴하다. 하지만 평균적으로 nlogn 의 성능을 내기때문에 예외를 둔다.