# -*- coding: utf-8 -*-

def merge(array, start, middle, end):
  n1 = middle - start + 1  # 第一個(gè)子序列長(zhǎng)度
  n2 = end - middle  # 第二個(gè)子序列長(zhǎng)度
  left_array = []
  right_array = []
  for i in range(n1):
    left_array.append(array[start + i])
  for i in range(n2):
    right_array.append(array[middle + i + 1])
  left_array.append(float('Inf'))  # float('Inf') 表示正無窮
  right_array.append(float('Inf'))
  i = j = 0
  for index in range(start, end + 1):
    if (left_array[i] <= right_array[j]):
      array[index] = left_array[i]
      i += 1
    else:
      array[index] = right_array[j]
      j += 1
  return array

def merge_sort(array, start, end):
  if start < end:
    middle = (start + end) // 2
    merge_sort(array, start, middle)
    merge_sort(array, middle + 1, end)
    merge(array, start, middle, end)

array = [1, 9, 2, 6, 7, 8, 8, 7, 9, 11, 18, 12, 13]
merge_sort(array, 0, len(array) - 1)
print(array)