Merge Sort

Il linguaggio permette approcci molto diversi per lo stesso algoritmo

def merge_sort(lista):
    n = len(lista)
    if(n > 1):
        centro = n // 2
        lista1 = lista[:centro]
        lista2 = lista[centro:]
        merge_sort(lista1)  # Ordina la 1° parte
        merge_sort(lista2)  # Ordina la 2° parte 

        n1 = len(lista1)
        n2 = len(lista2)
        i = j = k = 0
        while(i < n1) and (j < n2):
            if(lista1[i] <= lista2[j]):
               lista[k] = lista1[i]
               i += 1
            else:
               lista[k] = lista2[j]
               j += 1
            k += 1
        while(i < n1):
            lista[k] = lista1[i]
            i += 1
            k += 1
        while(j < n2):
            lista[k] = lista2[j]
            j += 1
            k += 1