timsort.py

RUN = 32

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

def merge(array, left, mid, right):
    len1 = mid - left + 1, 
    len2 = right - mid
    left_array, right_array = [], []
    
    for i in range(0, len1):
        left_array.append(array[left + i])
    for i in range(0, len2):
        right_array.append(array[mid + 1 + i])

    i, j, k = 0, 0, left
    while i < len1 and j < len2:
        if left_array[i] <= right_array[j]:
            array[k] = left_array[i]
            i += 1
        else:
            array[k] = right_array[j]
            j += 1
        k += 1

    while i < len1:
        array[k] = left_array[i]
        k += 1
        i += 1

    while j < len2:
        array[k] = right_array[j]
        k += 1
        j += 1

def tim_sort(array):
    """ Best: O(n) Average: O(nlogn) Worst: O(nlogn) | O(n) """
    n = len(array)
    for i in range(0, n, RUN):
        insert_sort(array, i, min((i + RUN - 1), n - 1))

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

        size = size * 2

array = [5, 2, 8, 4, 1, 9, 6, 3, 7]
tim_sort(array)
print(array)