[알고리즘]병합정렬(Merge Sort)

박주연·2022년 12월 6일
0

Algorithm

목록 보기
8/12

병합 정렬은 분할 정복(divide and conquer) 알고리즘을 사용하는 정렬 방식이다.

병합 정렬



병합 정렬은 분할 정복(divide and conquer) 알고리즘의 하나이다.
문제를 작은 단위로 쪼갠 뒤 작은 문제부터 해결하여 큰문제를 해결한다.

병합 정렬의 과정

병합 정렬의 과정은 다음과 같다.
1. 정렬되지 않은 초기 리스트(array[p..q])가 주어진다.
(p는 첫번째 인덱스, q는 마지막 인덱스)
2. 분할 :

  • p와 q의 중간점 r을 찾아 두 개의 리스트로 쪼갠다.
  • r = p+q/2의 계산 결과값을 내림하여 정수 r을 찾는다.
  • array[p..r] 과 array[r+1..q]로 나누어진다.

3. 정복 : 분할된 두개의 하위 배열을 각각 재귀적으로 정렬한다.

4. 병합 : 정렬된 두개의 배열을 하나의 정렬된 배열로 결합한다.

탈출조건
2개 미만의 요소가 포함된 하위 배열
(요소가 하나도 없거나 하나만 있는 하위 배열은 이미 정렬되어 있는 것과 같다.)

시간복잡도
O(NlogN)

병합 정렬 예제

병합정렬의 장단점

  • 장점: 시간 복잡도가 O(N^2)인 버블/삽입/ 선택 정렬에 비해 성능이 좋다.
  • 단점: 과정 중에 임시로 저장하는 배열이 따로 필요하기 때문에 메모리적인 측면에서는 불리하다.

참고문헌

profile
Zoë Park

0개의 댓글