병합 정렬 (Merge Sort) 정리

👩‍💻 병합 정렬 (Merge Sort) 정리 with Python

🍳 병합 정렬 (Merge Sort)이란?

1. 재귀 용법을 활용한 정렬 알고리즘입니다.
2. 리스트를 절반으로 잘라 비슷한 크기의 두 리스트로 나눕니다.
3. 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬합니다.
4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 병합합니다.

 Merge Sort는 Divide And Conquer의 대표적인 예시 알고리즘입니다.

 

🥘 병합 정렬 구현 with Python

def mergeSort(data):
    if len(data) <= 1:
        return data
    medium = len(data) // 2
    left = mergeSort(data[:medium])
    right = mergeSort(data[medium:])
    return merge(left, right)


def merge(left, right):
    merged = list()
    leftPoint, rightPoint = 0, 0

    while len(left) > leftPoint and len(right) > rightPoint:
        if left[leftPoint] > right[rightPoint]:
            merged.append(right[rightPoint])
            rightPoint += 1
        else:
            merged.append(left[leftPoint])
            leftPoint += 1
    while len(left) > leftPoint:
        merged.append(left[leftPoint])
        leftPoint += 1

    while len(right) > rightPoint:
        merged.append(right[rightPoint])
        rightPoint += 1

    return merged

 

 

🍪 시간 복잡도 분석

O(n) * O(log n) = O(n log n)