알고리즘 4 [병합정렬, merge sort]

4. 병합정렬(merge sort)

By Swfung8 - 자작, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=14961648

 

병합 정렬이란?
정렬되지 않은 리스트를 균등한 크기로 분할 후, 정복, 결합을 통해 정렬된 상태로 만드는 것

 

 

---

e.g.) 오름차순 병합정렬

[ 27, 10, 12, 20, 25, 13, 15, 22]의 배열이 있을때 각 데이터를 분할하여 비교하는 과정을 거치면서 병합

1. [27] vs [10], [12] vs [20], [25] vs [13], [15] vs [22]
2. [10, 27] vs [12, 20], [13, 25] vs [15, 22]
3. [10, 12, 20, 27] vs [13, 15, 22, 25]
4. [10, 12, 13, 15, 20, 22, 25, 27] 오름차순 완성!

---

[ 장점 ]

• 안정적인 정렬 형태
• 시간복잡도 면에서 굉장히 효율적임

[ 단점 ]

• 데이터가 배열로 구성되면 임시 배열이 필요하기 때문에 추가공간이 요구됨
• 데이터가 많으면 이동횟수가 많기 때문에 비효율을 초래함

시간 복잡도 : O(nlogn)
공간 복잡도 : O(n)