# Ces programmes sont sous licence CeCILL-B V1.

from math import *
from random import *

def fusion (tab,x,n,y,p,tab1,i):
  if x <= n and (y > p or tab[x] < tab[y]):
    tab1[i] = tab[x]
    fusion(tab,x+1,n,y,p,tab1,i+1)
  elif y <= p:
    tab1[i] = tab[y]
    fusion(tab,x,n,y+1,p,tab1,i+1)

def tri (tab,n,p):
  if n < p:
    k = (n + p) // 2
    tri(tab,n,k)
    tri(tab,k+1,p)
    tab1 = [0 for i in range(0,p+1)]
    fusion(tab,n,k,k+1,p,tab1,n)
    for i in range(n,p + 1):
      tab[i] = tab1[i]

tab = [0 for i in range(0,16)]
for i in range(0,16):
  tab[i] = floor(random() * 1000)

for i in range(0,16):
  print(tab[i],end="")
  print(" ",end="")
print()

tri(tab,0,15)
      
for i in range(0,16):
  print(tab[i],end="")
  print(" ",end="")
print()