병합 정렬(Merge Sort) : 효율적인 정렬 알고리즘 배우기

병합 정렬이란?

지난 강의에서 다양한 정렬 알고리즘을 배웠다. 선택 정렬, 버블 정렬 등은 이해하기 쉽지만, 실행 시간이 상대적으로 오래 걸린다. 이번에는 보다 효율적인 정렬 방법인 병합 정렬(Merge Sort) 에 대해 알아보자.

병합 정렬은 분할 정복(Divide and Conquer) 기법을 활용하는 정렬 알고리즘이다. 데이터를 반씩 나누고, 더 이상 나눌 수 없을 때까지 나눈 후, 다시 정렬하면서 합쳐나간다. 이러한 방식 덕분에 시간 복잡도가 O(n log n) 으로, 이전에 배운 선택 정렬(O(n²))보다 훨씬 빠르다.

 

병합 정렬의 동작 방식 🔍

1. 데이터 분할하기

정렬할 숫자들이 있다고 가정하자.

7 4 5 2 6 3 8 1

이 숫자들을 반으로 나눈다.

7 4 5 2 | 6 3 8 1

반으로 나눈 데이터 중 왼쪽 부분을 다시 반으로 나눈다.

7 4 | 5 2 | 6 3 8 1

한 번 더 나누면 다음과 같이 된다.

7 | 4 | 5 2 | 6 3 8 1

이제 숫자가 한 개씩 남을 때까지 계속 나눈다.

 

2. 정렬하며 병합하기 🛠

이제 숫자가 하나씩 남았으니, 다시 정렬하면서 병합 한다.

4와 7을 비교해서 작은 숫자가 먼저 오도록 정렬한다.

4 7 | 5 2 | 6 3 8 1

5와 2도 정렬한다.

4 7 | 2 5 | 6 3 8 1

이제 4 7과 2 5를 병합한다. 각 숫자를 차례로 비교하여 작은 숫자부터 배치 한다.

2 4 5 7 | 6 3 8 1

오른쪽 부분도 같은 과정을 거쳐 정렬한다.

2 4 5 7 | 1 3 6 8

마지막으로 두 부분을 병합하면 정렬이 완료된다.

1 2 3 4 5 6 7 8

 

 

병합 정렬의 시간 복잡도 ⏳

병합 정렬의 시간 복잡도는 O(n log n) 이다.

• 데이터를 반으로 나누는 과정 → O(log n)
• 나눈 데이터를 병합하는 과정 → O(n)
• 따라서 전체 시간 복잡도는 O(n log n) 이다.

이는 선택 정렬(O(n²))이나 버블 정렬(O(n²))보다 훨씬 효율적이다.

병합 정렬의 장점과 단점 📌

✅ 장점

• 빠르다: O(n log n)으로 대부분의 경우 선택 정렬, 버블 정렬보다 훨씬 빠름.
• 안정 정렬(Stable Sort): 동일한 값이 있을 때 기존 순서를 유지함.
• 큰 데이터에도 효율적: 입력 크기가 커질수록 장점이 더 두드러짐.

❌ 단점

• 추가적인 메모리 사용: 배열을 분할하고 병합하는 과정에서 O(n) 의 추가 공간이 필요함.
• 재귀 호출로 인한 오버헤드: 재귀를 많이 사용하기 때문에 호출 스택의 부담이 있을 수 있음.

---

+ 정리 

• 병합 정렬은 분할 정복(Divide and Conquer) 알고리즘 을 활용하여 데이터를 정렬한다.
• 실행 시간은 O(n log n) 으로 선택 정렬이나 버블 정렬보다 효율적이다.
• 추가적인 메모리 공간(O(n)) 이 필요하지만, 정렬 속도가 빠르고 안정적인 장점이 있다.