def wprowadzDane():
    noweDane = []
    while True:
        liczbaDanych = int(input("Podaj liczbe danych: "))
        if 0 < liczbaDanych <= 100:
            break
        print("Niepoprawna liczba danych, wprowadz ponownie: ")
    print("Wprowadz dane: ")
    for i in range(liczbaDanych):
        noweDane.append(int(input(f"Podaj element nr {i}: ")))
    return noweDane

def wyprowadzDane(doWypisania):
    print(" ".join(map(str, doWypisania)))

def scalPosortowaneCiagi(d1, d2):
    wynik = []
    ia, ib = 0, 0

    while ia < len(d1) and ib < len(d2):
        if d1[ia] < d2[ib]:
            wynik.append(d1[ia])
            ia += 1
        elif d1[ia] > d2[ib]:
            wynik.append(d2[ib])
            ib += 1
        else:
            wynik.append(d1[ia])
            ia += 1
            wynik.append(d2[ib])
            ib += 1

    # poniższą pętlę można napisać zwięźlej: wynik.extend(d1[ia:])
    while ia < len(d1):
        wynik.append(d1[ia])
        ia += 1

    # poniższą pętlę można napisać zwięźlej: wynik.extend(d2[ib:])
    while ib < len(d2):
        wynik.append(d2[ib])
        ib += 1

    return wynik

def sortujPrzezScalanieR(d, lewy, prawy):
    if lewy < prawy:
        srodek = lewy + (prawy - lewy) // 2
        wynikLewy = sortujPrzezScalanieR(d, lewy, srodek)
        wynikPrawy = sortujPrzezScalanieR(d, srodek + 1, prawy)
        return scalPosortowaneCiagi(wynikLewy, wynikPrawy)
    else:
        return [d[lewy]]

ciag3 = wprowadzDane()
wynik = sortujPrzezScalanieR(ciag3, 0, len(ciag3) - 1)
print("*** Ciag scalony")
wyprowadzDane(wynik)