ALGORITMOS DE ORDENAMIENTO

ORDENAMIENTO POR MEZCLA O MERGE SORT
ESTRUCTURAS DE DATOS II
INTEGRANTES: KEVIN BARRIOS, JEFFERSON CANOLES, MARIA PRIMERAS, KATHY RIOS Y MARIA CONTRERAS

DEFINICIÓN
 MergeSort es un algoritmo deordenamiento muy eficiente que utiliza la técnica

"divide y vencerás". Su orden asintótico es O(n*log(n)).
 Para ordenar un vector lo divide por la mitad en dos segmentos y ordena cada
segmento deforma recursiva ósea nuevamente divide cada segmento y ordena
los subsegmentos de forma recursiva... hasta que en algún momento los
segmentos serán de longitud
es cuando se llama a la función "merge"(mezclar) que intercala los elementos del ultimo segmento dividido colocando
primero los elementos menores.

SE BASA EN…..
 Este método se basa en la siguiente idea:

Si la lista es pequeña (vacía o detamaño 1) ya está ordenada y no hay nada que
hacer. De lo contrario hacer lo siguiente:
1. Dividir la lista al medio, formando dos sublistas de (aproximadamente) el mismo

tamaño cada una.
2. Ordenarcada una de esas dos sublistas (usando este mismo método).
3. Una vez que se ordenaron ambas sublistas, intercalarlas de manera ordenada.
Ejemplo en la siguiente presentación

EJEMPLO SI LA LISTA ESPEQUEÑA (VACÍA O DE TAMAÑO 1)

Si la lista original es:
[6, 7, -1, 0, 5, 2, 3, 8] 
deberemos ordenar recursivamente [6, 7, -1, 0] y [5, 2, 3, 8] 
con lo cual obtendremos [-1, 0, 6, 7] y [2, 3, 5,8].
Si intercalamos ordenadamente las dos listas ordenadas obtenemos la
solución buscada: [-1, 0, 2, 3, 5, 6, 7, 8].

DISEÑAMOS LA FUNCIÓN MERGE_SORT(LISTA):

Si lista es pequeña (vacía o de tamaño 1)ya está ordenada y no hay nada que
hacer. Se devuelve lista tal cual.
De lo contrario:
medio = len(lista)/2
izq = merge_sort(lista[:m])
der = merge_sort(lista[m:])
Se devuelve merge(izq, der)

ESQUEMADE MERGE SORT
El esquema es el siguiente:
Ordenar(lista L)
inicio
si tamaño de L es 1 o 0 entonces
devolver L
si tamaño de L es >= 2 entonces
separar L en dos trozos: L1 y L2.
L1 = Ordenar(L1)
L2 =...