합병 정렬 (Merge Sort)
이미 정렬된 리스트 2개 → 1개의 정렬된 리스트
시간 복잡도 : O(n-l+1) . [ n-l+1 = 원소 수]
| init List | 3 | 4 | 8 | 10 | 2 | 6 | 8 | 9 |
| ↑ l |
↑ m |
↑ m+1 |
↑ n |
|||||
| i1 | i2 | |||||||
| merged List | 2 | 3 | 4 | 6 | 8 | 8 | 9 | 10 |
반복 합병 정렬
입력 열의 길이가 1인 n개의 정렬된 List를 합병하여 길이가 2인 List 생성
길이가 2인 n/2개의 List를 합병하여 길이가 4인 List 생성
길이가 n인 List로 최종 합병될 때까지 계속
'알고리즘' 카테고리의 다른 글
| 정렬(Sorting) - 퀵 정렬 (Quick Sort) (0) | 2020.07.31 |
|---|---|
| 정렬(Sorting) - 삽입 정렬 (Insertion Sort) (0) | 2020.07.31 |
| 탐색 (Search) - 순차탐색, 이진탐색 (0) | 2020.07.29 |
| 그래프 (Graph) - 최단 경로 (Dijkstra, Ford 알고리즘) (0) | 2020.07.28 |
| Prim 알고리즘 (0) | 2020.07.28 |
