📌 합병 정렬
: 동일한 크기의 두 부분 배열로 분할하여 두 부분 배열을 순환적으로 정렬한 후 합병하는 방식
- 분할 정복 방식
- 두 부분 배열의 크기가 항상 같에 분할됨
✅ 분할(Divide)
: 정렬할 n 원소의 배열을 n/2 원소의 두 부분 배열로 분할함
✅ 정복(Conquer)
: 부분 배열을 정렬. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 방법을 적용함
✅ 합병(Combine)
: 정렬된 부분 배열들을 하나의 배열에 합병함
🔎
1. n/2로 두 부분 배열로 분할함
2. 분할을 계속 후 부분 배열의 크기가 최소일 때 정렬하여 합병함
:
❗ 합병 정렬 특징
- 최악의 수행 시간: O(nlogn)
- 레코드의 크기가 큰 경우 이동 횟수가 많음 ➡ 시간 낭비
- 안정적 정렬 방법이지만 제자리 정렬은 아님(O(n)만큼의 메모리 공간이 필요함)
- 실행 시간: T(n) = O(nlogn)
