합병 정렬(Merge Sort)

🟩 방법

1. 하나의 리스트를 두 개의 균등한 크기로 분할 (부분 리스트의 사이즈가 1이 될 때까지)

2. 분할된 리스트들을 정렬한 후

3. 정렬된 부분 리스트들을 하나로 합치면서 전체가 정렬된 리스트가 되게 하는 방법

 

🟩 분할정복 알고리즘

하나의 문제를 동일한 유형의 작은 문제들로 분할한 다음에

작은 문제에 대한 결과를 조합해서 큰 문제를 해결하는 방식의 알고리즘

 

🟩 시간 복잡도 O(nlogn)

데이터를 절반씩 분할하면서 줄여나가기 때문에 logn만큼의 분할이 이뤄지게 되고

각 분할에서 n번의 값 비교를 통해 위치를 찾아가기 때문에 O(nlogn)

cf. 퀵 정렬은 피봇을 어떻게 선택하느냐에 따라 최악의 시간 복잡도가 O(n^2)가 되지만, 합병정렬은 항상 리스트를 절반으로 나누기 때문에 O(nlogn)의 시간복잡도를 보장한다.

 

🟩 장단점

(장) 시간복잡도 보장

(장) 선택정렬, 삽입정렬 등의 시간복잡도 O(n^2)보다 효율적이다.

(단) 데이터가 배열로 구성된 경우, 임시 배열이 필요하므로 추가 공간 필요

👉 추가 공간을 사용하므로 제자리 정렬X

(단) 데이터의 크기가 큰 경우 이동 횟수가 많으므로 시간 낭비 발생