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