[이론] 병합 정렬 알고가기

인류 역사상 최고의 천재는 누구인가.

 

바로 나야 

 

그렇다, 인류 역사상 최고의 천재, 천재 중의 천재로 불리는 존 폰 노이만❗
이번에는 그가 고안한 병합 정렬(Merge Sort)에 대해서 알아보자.

 

병합 정렬이란❓

병합 정렬(Merge Sort)은 분할 정복 방식을 사용하여 데이터를 처리하는 정렬 알고리즘입니다.
즉, 데이터를 작게 나누고, 나눈 데이터를 다시 정렬하고 합쳐서 최종적으로 정렬된 결과를 얻는 방식입니다.

 

병합 정렬의 시간 복잡도 평균값은 O(nlogn)입니다. ⌛

 

병합 정렬의 동작 과정 정리 📝

1. 분할(Divide)
   배열을 더 이상 나눌 수 없을 때까지 쪼갠다.
2. 정복(Conquer)
   각 부분 배열을 정렬한다.
3. 병합(Merge)
   정렬된 두 배열을 합쳐 하나의 정렬된 배열로 만든다.

 

병합 정렬 그림으로 이해하기 🖼️

초기 배열 [42, 32, 24, 60, 15, 5, 90, 45] 을 예로 들어, 분할 과정, 정복 과정, 그리고 병합 과정을 그림으로 살펴보겠습니다!

 

0️⃣ 초기 배열

 

1️⃣ 분할 과정

• 배열을 반복하여 반으로 나누고, 더 이상 나눌 수 없을 때 까지 계속 나눠줍니다.
• 분할 결과:  [42],[32],[24],[60],[15],[5],[90],[45]

 

2️⃣ 정복 과정

• 각 부분 배열을 정렬합니다.
• 정복 결과: [32,42],[24,60],[5,15],[45,90]

 

3️⃣ 병합 과정

• 정렬된 부분 배열을 병합합니다.
• 병합 결과: [24,32,42,60],[5,15,45,90]

 

4️⃣ 최종 병합

• 가장 작은 값부터 비교하여 하나의 배열로 병합
• 최종 결과: [5,15,24,32,42,45,60,90]

 

병합 정렬 마무리 🚀

병합 정렬처럼 복잡해 보이는 알고리즘도 그림과 함께 시각화하면 훨씬 이해하기 쉬워집니다.
하지만, 코드를 구현하고 이해하는 과정은 또 다른 도전일 수 있죠.

그러니 꼭❗ 직접 구현에 도전해 보세요! 😊