lesson1Title

lesson2Title

lesson3Title

lesson4Title

lesson5Title

lesson6Title

lesson7Title

lesson8Title

lesson9Title

lesson10Title

lesson11Title

lesson12Title

lesson13Title

lesson14Title

lesson15Title

lesson16Title

lesson17Title

pythonIntroAlgorithms2Chapter1Title

pythonIntroAlgorithms2Chapter2Title

pythonIntroAlgorithms2Chapter3Title

pythonIntroAlgorithms2Chapter4Title

def merge_sort(arr):
    if len(arr) > 1:
        # 배열을 두 부분으로 나눕니다
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        # 각 부분을 재귀적으로 정렬합니다
        merge_sort(L)
        merge_sort(R)

        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

        # L과 R의 나머지 요소들을 병합합니다
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

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

    return arr


array = [38, 27, 43, 3, 9, 82, 10]

# 병합 정렬 실행
sorted_array = merge_sort(array)
print("정렬된 배열:", sorted_array)

# 병합 정렬 구현 방법

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

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

<br />

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

```python title="재귀적 정렬 예시"
merge_sort(L)
merge_sort(R)
```

<br />

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

```python title="병합 예시"
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
```

<br />

## 시간 복잡도

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

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

2. `최선의 경우 시간 복잡도`: O(nlog n)

   - 병합 정렬은 최선의 경우에도 배열을 나누고 병합하는 과정이 동일하게 진행되므로 시간 복잡도는 변하지 않습니다.

3. `평균 시간 복잡도`: O(nlog n)

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