Merge Sort

El algoritmo de ordenamiento por mezcla (merge sort en inglés) es un algoritmo de ordenamiento externo estable basado en la técnica divide y vencerás. Es de complejidad O(n log n).

Conceptualmente, el ordenamiento por mezcla funciona de la siguiente manera:

1. Si la longitud de la lista es 0 ó 1, entonces ya está ordenada. En otro caso:
2. Dividir la lista desordenada en dos sublistas de aproximadamente la mitad del tamaño.
3. Ordenar cada sublista recursivamente aplicando el ordenamiento por mezcla.
4. Mezclar las dos sublistas en una sola lista ordenada.

El ordenamiento por mezcla incorpora dos ideas principales para mejorar su tiempo de ejecución:

1. Una lista pequeña necesitará menos pasos para ordenarse que una lista grande.
2. Se necesitan menos pasos para construir una lista ordenada a partir de dos listas también ordenadas, que a partir de dos listas desordenadas. Por ejemplo, sólo será necesario entrelazar cada lista una vez que están ordenadas.

A continuación se muestra el código para este tipo de ordenamiento en Python:

#MERGE SORT

def mergeSort(a):
    merge_sort(a,0,len(a)-1)

#Merge_Sort
def merge_sort(a,izq,der):
    if izq<der:
        mit=(izq+der)/2
        merge_sort(a,izq,mit)
        merge_sort(a,mit+1,der)
        merge(a,izq,der,mit)
       

#Merge
def merge(a,izq,der,mit):
    list=[]
    i=izq
    j=mit+1
    while(i<=mit and j<=der):
        if(a[i]<=a[j]):
            list.append(a[i])
            i=i+1
        else:
            list.append(a[j])
            j=j+1
    while(i<=mit):
        list.append(a[i])
        i=i+1
    while(j<=der):
        list.append(a[j])
        j=j+1
    for k in range(0,der-izq+1):
        a[izq+ k]=list[k]   

prueba = [1,50,34,2,7,788]
mergeSort(prueba)

print(prueba)