병합 정렬(Merge Sort)이란?

• 병합 정렬은 배열을 반으로 나누고, 각 부분을 정렬한 다음 병합하는 방식으로 정렬을 수행하는 알고리즘입니다.

• 분할: 배열을 두 부분으로 나눕니다.

• 정복: 각 부분을 개별적으로 정렬합니다.

• 병합: 정렬된 부분들을 하나의 배열로 합칩니다.

• 최악 시간 복잡도: O(nlog n) - 병합 정렬은 원소의 개수에 대해 로그 선형에 비례하는 시간이 소요됩니다.

1. 분할 단계: 리스트를 두 부분으로 나눕니다. 이 과정은 재귀적으로 계속됩니다.

2. 정복 단계: 각 부분을 개별적으로 정렬합니다.

3. 병합 단계: 정렬된 부분 배열들을 하나의 배열로 병합합니다.

4. 정렬 완료: 모든 부분 배열이 병합되어 완전히 정렬된 배열이 됩니다.

• 재귀적 접근: 문제를 작은 문제로 나누고, 이를 재귀적으로 해결합니다.

• 효율성: 분할 정복 방식은 대규모 데이터에 높은 효율성을 보입니다.