본문으로 건너뛰기

병합 정렬 구현 방법

병합 정렬 구현 방법

1. 분할: 원래의 리스트를 가능한 한 균등한 두 부분으로 나눕니다.

분할 예시
mid = len(arr) // 2
L = arr[:mid]
R = arr[mid:]

2. 재귀적 정렬: 각 부분을 재귀적으로 정렬합니다.

재귀적 정렬 예시
merge_sort(L)
merge_sort(R)

3. 병합: 정렬된 두 부분을 하나의 정렬된 리스트로 병합합니다.

병합 예시
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1

while i < len(L):
arr[k] = L[i]
i += 1
k += 1

while j < len(R):
arr[k] = R[j]
j += 1
k += 1

시간 복잡도

  1. 최악의 경우 시간 복잡도: O(nlog n)

    • 병합 정렬은 분할과 병합 과정에서 일정한 시간 복잡도를 유지합니다. 각 단계에서 배열을 반으로 나누고, 각 레벨에서 (n)의 작업을 수행합니다. 따라서, ( \log n ) 단계에서 총 ( n ) 작업을 수행하게 됩니다.
  2. 최선의 경우 시간 복잡도: O(nlog n)

    • 병합 정렬은 최선의 경우에도 배열을 나누고 병합하는 과정이 동일하게 진행되므로 시간 복잡도는 변하지 않습니다.
  3. 평균 시간 복잡도: O(nlog n)

    • 일반적인 경우에도 병합 정렬은 일정한 (O(n log n))의 시간 복잡도를 유지합니다. 배열의 초기 정렬 상태에 관계없이 동일한 작업 수행량이 필요합니다.