from random import randint  # random integer


def insert_elem(elem, start, stop):
    global data

    # если входной массив пустой
    # база рекурсии 0
    if start == stop == 0:
        data.append(elem)
        return

    # если наш срез состоит из одного элемента
    # база рекурсии 1
    n = stop - start
    if n == 1:
        if elem > data[start]:
            if start + 1 < len(data):
                data.insert(start + 1, elem)
                return
            # если нам нужно вставить элемент в конец массива + 1
            else:
                data.append(elem)
                return
        else:
            data.insert(start, elem)
            return

    # шаг рекурсии - ищем середину
    centre = start + n // 2
    if elem < data[centre]:
        insert_elem(elem, start, centre)
    elif elem > data[centre]:
        insert_elem(elem, centre, stop)
    else:
        data.insert(centre, elem)


a = open('input_source.txt', 'w', encoding='utf-8')
for i in range(16):
    a.writelines(str(randint(1, 1000)) + '\n')
    b = randint(0, 100)
    if b < 20:
        a.writelines("Print data\n")
a.close()

data = []
a = open('input_source.txt', 'r', encoding='utf-8')
for x in a.readlines():
    if x == "Print data\n":
        print(data)
    else:
        insert_elem(int(x), 0, len(data))
print(data)