본문으로 건너뛰기
실습하기

병합 정렬 구현 방법

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))의 시간 복잡도를 유지합니다. 배열의 초기 정렬 상태에 관계없이 동일한 작업 수행량이 필요합니다.

다음 내용이 궁금하다면?

코드프렌즈 PLUS 멤버십 가입 or 강의를 등록해 주세요!