[Sorting] 합병 정렬, Merge Sort

https://github.com/cuttingworms/Data-Structures-with-Python

GitHub - cuttingworms/Data-Structures-with-Python

- 합병 정렬 (Merge Sort)

• 크기가 n인 입력을 1/2n 크기로 분할하고, 각각에 대해 재귀적으로 합병 정렬을 수행한 후, 2개의 각각 정렬된 부분을 합병하는 정렬 알고리즘
•  수행 과정에서 임시로 합병된 결과를 저장하기 위해 입력 리스트 a와 같은 크기의 보조 리스트가 필요

Merge Sort, 출처 위키피디아

- 반복 합병 정렬 (Iterative Merge Sort)

• 입력 리스트에서 바로 두 개씩 짝지어 합병한 뒤, 다시 네 개씩 짝지어 합병하는 Bottom-up 방식으로 수행하는 합병 정렬 알고리즘

 

- 수행 시간

• 어떤 입력에 대해서도 O(nlog(n))의 수행 시간을 보장
• 입력 크기의 보조 리스트를 사용한다는 것이 단점 (Not in-place algorithm)