병합 정렬

🌱 병합 정렬(Merge sort)

분할 정복(divide and conquer) 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘

• 시간복잡도 평균값은 O(nlogn)

🌱 병합 정렬(Merge sort)의 핵심 이론

42 32 24 60 15 5 90 45

🔻

🟩 가장 작은 데이터 집합으로 분할
42 🔹 32🔹 24🔹 60🔹 15🔹 5 🔹90🔹 45

🔻

🟩 병합하면서 정렬1
32 42 🔹 24 60 🔹 5 15 🔹 45 90

🔻

🟩 병합하면서 정렬2
24 32 42 60 🔹 5 15 45 90

🔻

🟩 병합하면서 정렬3
5 15 24 32 42 45 60 90

🌱 병합 정렬(Merge sort)에서 2개의 그룹을 병합하는 과정

• 투 포인터 개념을 사용하여 왼쪽, 오른쪽 그룹을 병합
• 왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값을 결과 배열에 추가하고 포인터를 오른쪽으로 1칸 이동시킴