Merge sort

Divide-and-conquer를 기반으로 하는 대표적인 정렬 알고리즘.

 

주어진 배열 n을 2/n으로 계속 분할해,

각 부분 배열이 하나의 원소를 가질 때까지 나눈 다음,

이를 다시 정렬하면서 병합하는 방식으로 전체 배열을 정렬한다.

 

즉, 크게 3개의 과정으로 나뉜다.

1. Divide : 배열을 가운데 기준 두 부분으로 나누어준다. 🌐 O(1) (중간 인덱스만 알면 되니까)

2. Conquer : 나눠진 배열 각각에 대해 재귀적으로 mergesort를 적용해 정렬한다. 2번의 정렬 작업이 이뤄진다.

3. Combine : 정렬된 두 배열을 하나의 정렬된 배열로 병합한다. 🌐 O(n) (모든 원소를 한 번씩 비교해 합치니까)

 

이를 점화식으로 표현하면 아래와 같다.

 

✅ 분할이 log n 단계에 걸쳐 일어나고, 각 단계에서 O(n) 시간이 소요되어 항상 O(nlogn)의 시간 복잡도를 가진다.