Python, sorted()의 시간복잡도, timsort

0. 결론

결론부터 말하자면 O(NlogN)을 보장한다. 많이 사용되는 병합정렬의 한 유형인 퀵정렬도 최소일 경우 같은 시간복잡도를 보이지만 최대 O(N^2)일 수 있으니 sorted()는 안전한 정렬함수이다. 어떻게 보장했는지 간단하게 알아보자

sorted(array): 정렬된 array를 반환
array.sort(): array정렬

1. 원리

sorted()는 내부적으로 Timsort 알고리즘을 사용하여 정렬을 수행한다. Timsort는 병합 정렬과 삽입 정렬을 결합한 정렬 알고리즘이며, 평균 및 최악의 경우 시간 복잡도 O(NlogN)을 보장한다.

1) 간단한 이해를 위한 Timsort(진짜 Timsort는 아님)

• 작은 배열에 대해 삽입정렬을 사용한다.
• 배열을 일정한 크기의 런으로 나문다. 런은 이미 정렬된 연속적인 요소들의 시퀀스
• 각 런이 정렬된 후 이 런들을 병합정렬을 사용하여 병합
• 병합 과정의 반복, timsort함수는 병합의 크기를 min_run에서 시작하여 점차 두배씩 증가시키며 전체 배열이 정렬될 때 까지 병합 과정을 반복

def insertion_sort(arr, left, right):
    for i in range(left + 1, right + 1):
        temp = arr[i]
        j = i - 1
        while j >= left and arr[j] > temp:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = temp

def merge(arr, l, m, r):
    len1, len2 = m - l + 1, r - m
    left, right = [], []
    for i in range(0, len1):
        left.append(arr[l + i])
    for i in range(0, len2):
        right.append(arr[m + 1 + i])

    i, j, k = 0, 0, l
    while i < len1 and j < len2:
        if left[i] <= right[j]:
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1
        k += 1

    while i < len1:
        arr[k] = left[i]
        i += 1
        k += 1

    while j < len2:
        arr[k] = right[j]
        j += 1
        k += 1

def timsort(arr):
    n = len(arr)
    min_run = 32
    for start in range(0, n, min_run): # 삽입 정렬
        end = min(start + min_run - 1, n - 1)
        insertion_sort(arr, start, end)

    size = min_run
    while size < n:
        for left in range(0, n, 2 * size):
            mid = min(n - 1, left + size - 1)
            right = min((left + 2 * size - 1), (n - 1))
            if mid < right:
                merge(arr, left, mid, right)
        size = 2 * size

arr = [12, 11, 13, 5, 6, 7]
timsort(arr)
print("Sorted array is: ", arr)

2) 더 자세히

https://academic-accelerator.com/encyclopedia/kr/timsort
위의 링크를 따라가면 Timsort를 자세히 리뷰한 글이 있다. 요약하자면 timsort는 작은 데이터 세트에 대해 매우 효율적이며, 삽입 정렬을 같이 사용해 병합정렬의 최대 시간복잡도를 줄였다. 그리고 2015년 이 알고리즘에 오류를 발견했다고 한다. 큰 데이터, 입력의 경우 수용할 수 없는 언어들있다.(Java 등) 이 예외를 수정하여 다시 python,android등에 적용시킴으로 오류는 해결된 것으로 점식 검증 마쳤다고 한다.