Tim Sort

def insertion_sort(arr, l, r):
  N = len(arr)
  for i in range(l, r):
    j = min(range(i, r), key=arr.__getitem__)
    arr[i], arr[j] = arr[j], arr[i]


def merge(arr, brr):
  res = []

  i = j = 0
  while i < len(arr) and j < len(brr):
    if arr[i] < brr[j]:
      res.append(arr[i])
      i += 1
    else:
      res.append(brr[j])
      j += 1

  res.extend(arr[i:])
  res.extend(brr[j:])

  return res


def tim_sort(arr, r=5):
  N = len(arr)

  for i in range(0, N, r):
    insertion_sort(arr, i, min(i+r, N))

  while r < N:
    for i in range(0, N, 2*r):
      arr[i: i + 2*r] = merge(arr[i: i+r], arr[i+r: i + 2*r])
    r *= 2


if __name__ == '__main__':
  import random as rand

  for _ in range(1000):
    n = rand.randrange(10,100)
    l = [rand.randrange(-100, 101) for _ in range(n)]
    s = sorted(l)
    tim_sort(l)
    assert l == s
  print('Passed')