알고리즘 | 병합 정렬

✔ 학습목표

재귀를 활용한 병합 정렬을 구현할 수 있다.

 

병합 정렬

병합 정렬(merge sort)은 원소가 한 개가 될 때까지 계속해서 나누다가 다시 합쳐가며 정렬을 하는 방식이다. 합병 정렬이라고도 한다. 이는 분할 정복(divide and ) 알고리즘의 하나이다. 분할 정복은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음 결과를 모아 원래의 문제를 해결하는 전략이다.

 

병합 정렬의 단계

병합 정렬은 세 단계로 이루어진다.

 

1) 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.

2) 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할한다.

3) 결합(Combine): 정렬된 부분 배열들을 하나의 배열로 합친다.

 

숫자 8개를 오름차순으로 정렬하는 예시를 보자.

 

 

 

그림에서 처럼 분할(Divide) 단계가 끝나면 본격적으로 정복(Conquer)과 결합(Combine)이 일어난다. 값을 비교할 때는 각 배열의 앞에서부터 숫자를 순서대로 읽어 들이고, 더 작은 숫자를 병합되는 부분에 가져온다.

 

병합 정렬의 효율성

병합 정렬 실행시간의 상한은 O(n log n)이다. 숫자들을 합치는 데 O(log n)의 시간이 걸리고(8개의 숫자가 있다면 3단계), 각 병합 단계에서 비교하는데 O(n)의 시간이 걸리기 때문에 이들을 곱해서 계산한다. 하한도 역시Ω(n log n)이다. 정렬 여부에 관계없이 모든 과정이 진행된다.

 

병합 정렬의 장단점

병합 정렬에서 만약 레코드를 배열로 구성하면 임시 배열이 필요하다. 이는 선택 정렬이나 버블 정렬과 달리 제자리 정렬(in-place sorting)이 아니다. 그렇기에 추가적인 메모리가 필요하다. 하지만 실행 시간의 상한이 낮아 빠른 정렬이 가능하다는 장점이 있다.

 

정렬 비교

이름	O	Ω
선택 정렬	n^2	n^2
버블 정렬	n^2	n^2
병합 정렬	n log n	n log n

 

참고 자료

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

 

---

 

이 글은 네이버 부스트 코스 David J. Malan(데이비드 J. 말란) 교수님의 모두를 위한 컴퓨터 과학(CS50 2019) 강의를 수강하고 작성한 글입니다. 본 강좌 내 실습에서는 CS50 Sandbox를 사용합니다.

 

모두를 위한 컴퓨터 과학 (CS50 2019)