정렬 알고리즘 - Merge Sort

병합 정렬 이란?

배열을 절반씩 계속 잘라서 가장 작은 조각들을 기준으로 정령, 병합하는 방식

장점

• 데이터분포에 상관없이 시간 복잡도는 O(nolog2n)으로 동일하다
• 레코드를 연결리스트(Linked List)로 구성하면, 링크 인덱스만 변경되기 때문에 데이터의 이동에 필요한 리소스는 작아진다.
• 따라서 연결리스트를 정렬할때는 Linked List 자료형을 사용하는 것이 좋다.

단점

• 배열로 구성하게 되면 임시 배열이 필요하다.
• 레코드의 크기가 큰 경우 이동횟수가 많으므로 시간정 낭비를 초래한다.