# Invariante di ciclo: all'inizio di ogni iterazione del ciclo
# 'while', l'array X contiene gli i+j elementi piu' piccoli tra quelli
# contenuti in L ed R ed ordinati. Inoltre, gli elementi L[i] ed R[j]
# sono i piu' piccoli dei loro arrays non ancora copiati in X
# Inizializzazione: banale, i=j=0 e X vuoto. Inoltre L[0] e R[0] sono
# i piu' piccoli di L ed R, rispettivamente, dato che L e R sono
# ordinati per ipotesi.

# Mantenimento: Dopo aver eseguito il corpo del ciclo, X contiene solo
# un elemento piu' di prima e questo e' il piu' piccolo tra L[i] e
# R[j], che per ipotesi induttiva sono i piu' piccoli non ancora
# copiati in X. Uno dei due indici e' stato incrementato quindi adesso
# X contiene gli i+j elementi piu' piccoli di L e R. Se la condizione
# di 'if' era vera, allora i e' stato incrementato di uno e adesso
# L[i] e' il piu' piccolo elemento di L non ancora copiato in X, dato
# che L e' ordinato. Il caso opposto e' analogo considerando R e j.

# Al termine dei ciclo ci sono due casi possibili: (1) i!=len(L) e
# j==len(R), oppure (2) i==len(L) e j!=len(R).  Nel caso (1), al
# termine del ciclo l'invariante garantisce che tutti gli elementi di
# L[i:] siano piu' grandi di quelli contenuti in X, che sono quelli
# nell'unione di R con L[:i]. Quindi l'istruzione 'if' seguente
# garantisce che venga ritornata l'unione di L con R, ordinata. Il
# caso (2) e' analogo, considerando stavolta L e R[j:].


# Differenze tra python e lo pseudo-codice:
# (1) len(A) ritorna la lunghezza di A, usato al posto di A.length

# (2) Gli indici partono da 0 come in C. I sottoarrays (slices) si
# indicano con ':' anziche' con '..' e l'ultimo indice del range non
# e' incluso. Quindi A[2..3] dello pseudo codice diventa A[1:3] in
# python. P.es. se A=[2,5,7,3,4], allora A[1:3] == [5,7]

# (3) A.append(x) appende l'oggetto x alla sequenza A. Notate che le
# sequenze di python possono essere 'eterogenee' ovvero contenere
# oggetti di tipo diverso tra loro. Quindi p.es. se A=[1,2,3] e
# B=[4,5], il risultato di A.append(B) e' [1,2,3,[4,5]]. Per ottenere
# [1,2,3,4,5] va usato A.extend([4,5])

# Nota sul passaggio dei parametri alle funzioni: in python tutto e'
# un oggetto, le variabili non rappresentano 'scatole' che contengono
# oggetti come in C/Java, ma nomi associati agli oggetti. Infatti
# un'assegnazione in python dove a sinistra ccompare una variabile,
# non e' una scrittura in memoria bensi' l'associazione tra l'oggetto
# a destra e la variabile a sinistra. P.es. scrivendo A=[2,5,7,3,4] e
# poi B=A, l'assegnazione non determina una copia della sequenza.  Per
# convincersene, il seguente codice: A=[2,5,7,3,4]; B=A; B[0]=9; print
# A stampa la sequenza [9, 5, 7, 3, 4]. 

# In modo analogo, i parametri delle funzioni sono nomi associati con
# gli oggetti ad esse passati. Non viene effettuata alcuna copia. Ma
# non si ottengono neanche effetti per il chiamante come con le
# rererences del C, p.es. scriviamo la funzione def foo(a): a=2 adesso
# x=4; foo(x); print x stampa 4, quello che accade in dettaglio e'
# semplice: foo riceve il nome a associato con l'oggetto (numero) 4,
# poi l'assegnazione a=2 associa il nome a con l'oggetto (numero) 2,
# perdendo il riferimento a 4. Il chiamante non vede nulla.  Le
# conseguenze dell'approccio python sono un diverse se l'oggetto
# passato e' 'mutabile', ovvero modificabile, come p.es. una lista. In
# questo caso se scriviamo def foo(a): a[0]=2 e poi c=[1,2,3]; foo(c);
# print c il chiamante vede la modifica. Infatti, l'assegnazione
# a[0]=2 rappresenta una modifica all'oggetto a cui era associato il
# nome a, lo stesso oggetto a cui era associato il nome c nel
# chiamante.



def merge(L,R):
    """
    Given two sorted sequences L and R, return their merge.
    """
    i = 0
    j = 0
    X = []
    while i<len(L) and j<len(R):
        if L[i]<R[j]:
            X.append(L[i])
            i += 1
        else:
            X.append(R[j])
            j += 1
    if i<len(L):
        X.extend(L[i:])
    else:
        X.extend(R[j:])
    return X

def merge_sort(A):
    """
    Sort list A into order, and return result.
    """
    n = len(A)
    if n==1: 
        return A
    mid = n//2     # floor division
    L = merge_sort(A[:mid])
    R = merge_sort(A[mid:])
    return merge(L,R)