'''merge или спајање две сортиране листе у једну сортирану листу (учешљавање)
На пример, за улаз
lista1 = [1, 3, 4, 7, 9]
lista2 = [2, 5, 6, 8]
резултат треба да буде
lista = [1, 2, 3, 4, 5, 6, 7, 8, 9]
'''

lista1 = [1, 3, 4, 7, 9]
#lista1 = []
#lista1 = [4]
lista2 = [2, 5, 6, 8]
#lista2 = []
#lista2 = [6]

pozicija1 = 0 #позиција у 1. листи
pozicija2 = 0 #позиција у 2. листи

duzina1 = len(lista1) #дужина 1. листе
duzina2 = len(lista2) #дужина 2. листе

lista = [] #резултат, спојене листе lista1 и lista2 у једну сортирану листу

#све док нисмо дошли до краја ниједне од двеју листи
#преписујемо мањи почетни елемент у нову листу;
#ако су почетни елементи једнаки, преписујемо оба
while pozicija1 < duzina1 and pozicija2 < duzina2:
    if lista1[pozicija1] < lista2[pozicija2]:
        lista.append(lista1[pozicija1])
        pozicija1 += 1
    elif lista2[pozicija2] < lista1[pozicija1]:
        lista.append(lista2[pozicija2])
        pozicija2 += 1
    else:
        lista.append(lista1[pozicija1])
        pozicija1 += 1
        lista.append(lista2[pozicija2])
        pozicija2 += 1

#испразнила се једна листа или чак обе, па преостале елементе, ако их има, само треба преписати
#извршиће се највише једна од следећих петљи, а можда и ниједна

while pozicija1 < duzina1:
    lista.append(lista1[pozicija1])
    pozicija1 += 1

while pozicija2 < duzina2:
    lista.append(lista2[pozicija2])
    pozicija2 += 1

print(lista)