합병 정렬은 주어진 n길이의 리스트에서 작은 집합을 여러개 만들어 비교하고
여러 집합을 병합해과는 과정에서 리스트를 정렬해나가는 방법이다.
1. 분할단계는 리스트를 성분이 2개가 될 때까지 분할한다.
2. 병합단계는 2개의 성분을 가진 리스트에서 정렬하여 병합된 리스트에 삽입한다.
3. 모든 리스트가 주어진 길이 n이 될 때까지 병합을 반복한다
합병정렬의 방법
출처: https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC
합병 정렬 - 위키백과, 우리 모두의 백과사전
합병 정렬 또는 병합 정렬(merge sort)은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 존 폰 노이만이 1945
ko.wikipedia.org
합병정렬은 분할과정과 병합과정에서 리스트 길이 n에 따른 동일한 시간을 소모하므로
시간복잡도는 O(nlogn) Ω(nlogn) 이 된다.
'Language > Algorithm' 카테고리의 다른 글
5. 힙 트리 ( Heap Tree ) (0) | 2021.12.17 |
---|---|
3. 버블 정렬 (0) | 2021.12.15 |
2. 선택 정렬 (0) | 2021.12.13 |
1.이진탐색트리 (BST) (0) | 2021.12.12 |