#09. 합병 정렬, 병합 정렬(Merge Sort)

합병 정렬, 병합 정렬(Merge Sort)

• 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬하는 방식
• 실행 시간의 상한은 O(n log n)
• 실행 시간의 하한도 역시 Ω(n log n)

---

 

병합 정렬(합병 정렬)은 전화번호부의 분할 정복 탐색처럼 데이터를 반으로 나누어간다는 것과 공통점이 있다.

 

그리고 이 과정은 재귀적으로 구현되기 때문에 재귀를 학습하면 더 이해하기 쉽다.

 

병합 정렬의 실행 시간의 상한은 O(n log n)이다.

 

숫자들을 반으로 나누는 데는 O(log n)의 시간이 들고, 각 반으로 나눈 부분들을 다시 정렬해서 병합하는 데 각각 O(n)의 시간이 걸리기 때문이다.

 

실행 시간의 하한도 역시 Ω(n log n)이다. 숫자들이 이미 정렬되었는지 여부에 관계없이 나누고 병합하는 과정이 필요하기 때문이다.

 

---

References

 

dpdpwl.tistory.com/53

[Algorithm]합병정렬(merge sort) 알고리즘 C++