[Python] 파이썬 기본 정렬 함수 알고리즘: 팀소트(Timsort)

Timsort

• 파이썬을 위해 고안한 정렬 알고리즘
• 애초에 학계에서 받아들여질 만한 우아한 알고리즘을 목표로 하기보다는 '실제 데이터는 대부분 이미 정렬되어 있을 것이다'라고 가정하고 실제 데이터에서 고성능을 낼 수 있도록 설계한 알고리즘
  • 즉, 실제 데이터는 대부분 이미 정렬되어 있을 것이라는 가정 하에 최적화
• 개별적인 단일 알고리즘이 아니라 삽입 정렬과 병합 정렬을 휴리스틱하게 적절히 조합해 사용하는 정렬 알고리즘

알고리즘	최선	평균	최악
퀵 정렬	n log n	n log n	n^2
병합 정렬	n log n	n log n	n log n
팀소트	n	n log n	n log n

 

작동 방식

1. 런(Run) 생성
   • 리스트를 순회하면서 오름차순(또는 내림차순)으로 정렬된 연속된 부분 리스트(런)를 찾음
   • 이때, 리스트의 길이가 짧으면 삽입 정렬을 사용하여 정렬
   • 기본적으로 최소 런 길이는 32로 설정
2. 런 정렬
   • 생성된 런을 병합 정렬 방식으로 병합
   • 이 과정에서 두 런을 병합할 때, 두 런의 크기와 비교하여 최적의 병합 순서를 결정

 

단계별 알고리즘

1. 분할
   • 입력 리스트를 여러 개의 작은 런으로 나눔
   • 각 런은 최소 길이를 가짐
2. 정렬
   • 각 런을 삽입 정렬을 통해 정렬
3. 병합
   • 정렬된 런을 병합하여 최종적으로 정렬된 리스트를 만듦

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

def merge(arr, l, m, r):
    len1, len2 = m - l + 1, r - m
    left, right = [], []

    for i in range(len1):
        left.append(arr[l + i])
    for i in range(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 tim_sort(arr):
    n = len(arr)
    min_run = 32

    for i in range(0, n, min_run):
        insertion_sort(arr, i, min((i + min_run - 1), n - 1))

    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