728x90
병합정렬(합병정렬)
병합정렬( Merge Sort )이란,
분할 정복 알고리즘(문제를 작은 2개로 분할하여 각각 해결한 뒤, 결과를 모아 원래 문제를 해결)중 하나이며,
입력 배열을 더 작은 하위 배열로 분해하고, 이러한 하위 배열들을 정렬한 다음 병합하여 정렬된 배열을 만드는 방법이다.
정렬 단계는 다음과 같다.
하위 배열이 하나의 요소로 이뤄질 때까지 배열을 반으로 재귀적으로 나눈다(divide).
하위 배열은 두 개의 가장 작은 요소를 비교하고 정렬(conquer)함으로써 쌍으로 병합(combine)된다.
모든 하위 배열들이 정렬된 단일 배열로 전부 병합될 때까지 반복된다.
장점
최악의 경우에도 시간 복잡도O(nlogn)가 버블/선택정렬O(n^2)보다 효율적이다.
안정적인 정렬 알고리즘이다. 여기서 '안정적이다'란, 입력 배열에서 동일한 요소의 상대적 순서가 정렬된 출력에서도 유지되는 경우를 말한다.
단점
정렬 단계 중, 하위 배열로 나누는 과정에서 하위 배열을 저장하기 위한 추가 메모리가 필요한데, 이는 큰 배열의 경우 문제가 될 수 있다.
다른 알고리즘에 비햏 오버헤드가 높기에, 작은 배열에는 최선의 선택이 아닐 수 있다.
728x90
'자료구조' 카테고리의 다른 글
| +) JAVA Eclipse 자바 이클립스 디버깅하는 방법 (0) | 2023.04.01 |
|---|---|
| +) [JAVA] 기수정렬 알고리즘 정리 - radix sort (0) | 2023.03.22 |
| +) [JAVA] 퀵정렬 알고리즘 정리 - quick sort (0) | 2023.03.22 |
| +) [JAVA] 버블정렬 알고리즘 정리 - bubble sort (0) | 2023.03.22 |
| +) [JAVA] 힙정렬 알고리즘 정리 - heap sort (0) | 2023.03.15 |