Merge Sort
Clase 03
IIC 2133 - Sección 1
Prof. Diego Arroyuelo
Sumario
Introducción
Merge
Merge Sort
Cierre
Complejidad de algoritmos de ordenación
Resumimos los resultados de complejidad por caso hasta el momento
Caso Memoria
Algoritmo Mejor caso Peor caso
promedio adicional
Selection Sort ? ? ? O(1)
Insertion Sort O(n) O(n2 ) O(n2 ) O(1)
Merge Sort ? ? ? ?
Quick Sort ? ? ? ?
Heap Sort ? ? ? ?
1 / 35
Complejidad de algoritmos de ordenación
Resumimos los resultados de complejidad por caso hasta el momento
Caso Memoria
Algoritmo Mejor caso Peor caso
promedio adicional
Selection Sort O(n2 ) O(n2 ) O(n2 ) O(1)
Insertion Sort O(n) O(n2 ) O(n2 ) O(1)
Merge Sort ? ? ? ?
Quick Sort ? ? ? ?
Heap Sort ? ? ? ?
2 / 35
SelectionSort in place
input : Secuencia A[0 . . . n − 1], largo n ≥ 2
output: ∅
SelectionSort (A, n):
1 for i = 0 . . . n − 2 :
2 min ← i
3 for j = i + 1 . . . n − 1 :
4 if A[j] < A[min] :
5 min ← j
6 A[i] ⇋ A[min]
3 / 35
SelectionSort e InsertionSort in place
SelectionSort (A, n): InsertionSort (A, n):
1 for i = 0 . . . n − 2 : 1 for i = 1 . . . n − 1 :
2 min ← i 2 j ←i
3 for j = i + 1 . . . n − 1 : 3 while (j > 0) ∧ (A[j] < A[j − 1]) :
4 if A[j] < A[min] : 4 A[j] ⇋ A[j − 1]
5 min ← j 5 j ←j −1
6 A[i] ⇋ A[min]
4 / 35
Ordenación hasta ahora
SelectionSort
No tiene un mejor caso que sea mejor que su peor caso: O(n2 )
Siempre revisa la secuencia completa para determinar el mı́nimo
InsertionSort
Cuando la secuencia está ordenada toma O(n)
En el caso promedio es O(n2 ), tomando el promedio sobre todas las
permutaciones igualmente probables
Argumentamos esto mediante conteo de inversiones en cada
permutación
¿Podemos tener un algoritmo de ordenación
con mejor complejidad que O(n2 ) en el peor caso?
5 / 35
Hay esperanza: corregir varias inversiones a la vez
Ejemplo
Recordemos que el siguiente arreglo tiene 9 inversiones
34 8 64 51 32 21
0 1 2 3 4 5
Si intercambiamos 34 y 8:
8 34 64 51 32 21
0 1 2 3 4 5
Corregimos (0, 1)
Si intercambiamos 34 y 21:
21 8 64 51 32 34
0 1 2 3 4 5
Corregimos (0, 4), (0, 5), (4, 5)
6 / 35
Un escenario relacionado
Consideremos una secuencia parcialmente ordenada
Para ser más precisos, una secuencia que está formada por dos
sub-secuencias ordenadas
8 20 29 40 50 60 70 82 15 32 41 65
1 2 3 4 5 6 7 8 9 10 11 12
Además, sabemos exactamente dónde comienza la segunda sub-secuencia
ordenada
¿Cómo aprovechamos este hecho para ordenar la secuencia completa?
7 / 35
Primer intento: InsertionSort
Estado inicial
A1 A2
8 20 29 40 50 60 70 82 15 32 41 65
1 2 3 4 5 6 7 8 9 10 11 12
InsertionSort no intercambia nada del tramo A1 y los ı́ndices i, j llegan al
tramo A2
j =9
8 20 29 40 50 60 70 82 15 32 41 65
1 2 3 4 5 6 7 8 9 10 11 12
i =9
Hasta este punto la ejecución es O(n)
8 / 35
Primer intento: InsertionSort
El valor 15 se va intercambiando hasta llegar a su posición final j = 2
j =2
8 15 20 29 40 50 60 70 82 32 41 65
1 2 3 4 5 6 7 8 9 10 11 12
i =9
En la siguiente iteración,
j = 10
8 15 20 29 40 50 60 70 82 32 41 65
1 2 3 4 5 6 7 8 9 10 11 12
i = 10
Conclusión: en este tramo el algoritmo vuelve a ser O(n2 )
Hoy veremos una mejor estrategia para aprovechar el orden
9 / 35
Objetivos de la clase
Comprender el algoritmo Merge para combinar secuencias ordenadas
Determinar complejidad de Merge y el trade off de ejecutarlo in place
Demostrar correctitud de Merge
Comprender el uso de Merge como algoritmo de ordenación general en
MergeSort
Determinar la complejidad de MergeSort
10 / 35
Sumario
Introducción
Merge
Merge Sort
Cierre
Mezcla (merge) de secuencias ordenadas
Proponemos el siguiente algoritmo para combinar dos secuencias ordenadas
para formar una nueva ordenada
input : Secuencias ordenadas A y B
output: Nueva secuencia ordenada C
Merge(A, B):
1 Iniciamos C vacı́a
2 Sean a y b los primeros elementos de A y B
3 Extraer de su secuencia respectiva el menor entre a y b
4 Insertar el elemento extraı́do al final de C
5 Si quedan elementos en A y B, volver a lı́nea 2
6 Concatenar C con la secuencia que aún tenga elementos
7 return C
11 / 35
Merge: Ejemplo de ejecución
a 8 8
20 a 20
29 29
40 40
A
50 50
60 60
C
70 70
82 82
b 15 b 15
32 32
B
41 41
65 65
Estado inicial Estado luego de la
primera iteración
12 / 35
Merge: Ejemplo de ejecución
8 8
a 20 15 15
29 a 29 20
40 40
50 50
60 60
70 70
82 82
b 32 b 32
41 41
65 65
Estado luego de la Estado luego de la
segunda iteración tercera iteración
13 / 35
Merge: Ejemplo de ejecución
8 8
15 15
20 20
29 29
32 32
40 40
70 41 41
82 50 50
60 60
65 65
70
82
Estado luego de insertar en C Estado luego de
el último elemento de B concatenar el resto de A
14 / 35
Correctitud de Merge
Demostración (finitud)
En cada iteración del algoritmo antes de ejecutar la lı́nea 6, se extrae
siempre un elemento de A o B, y se inserta en C .
Luego, cuando una de las secuencias se vacı́a, se insertan todos sus
elementos en C .
En total se realizan n = ∣A∣ + ∣B∣ inserciones y un número menor a n de
comparaciones entre elementos. Luego, el algoritmo termina en una
cantidad finita de pasos.
15 / 35
Correctitud de Merge
Demostración (propósito)
Para A, B inicialmente ordenadas, consideremos la propiedad
P(n) ∶= Luego de insertar el n-ésimo elemento en C ,
A, B, C se encuentran ordenadas
1. Caso base. P(1) corresponde al estado de las secuencia luego de
insertar el primer elemento en C .
● Dado que se extrajo el menor elemento de alguna de las otras
secuencias, estas se mantienen ordenadas. Esto aplica trivialmente
si dicha secuencia queda vacı́a.
● Dado que C solo tiene un elemento, está ordenada.
16 / 35
Correctitud de Merge
Demostración (propósito)
P(n) ∶= Luego de insertar el n-ésimo elemento en C ,
A, B, C se encuentran ordenadas
2. H.I. Suponemos que luego de agregar el n-ésimo elemento, A, B, C
están ordenadas.
P.D. Luego de agregar el (n + 1)-ésimo elemento, A, B, C siguen
ordenadas.
Tenemos dos casos
● Si quedan elementos en A y en B, sea cn+1 el menor entre las
cabezas de A y B.
● Sin pérdida de generalidad, si solo quedan elementos en A, sea
cn+1 la cabeza de A.
Se elimina cn+1 de su secuencia respectiva y se inserta al final de C .
17 / 35
Correctitud de Merge
Demostración (propósito)
Por H.I. tenemos que la secuencia de origen de cn+1 se encontraba ordenada
antes de sacarlo. Como es el mı́nimo de la secuencia por ser el primer
elemento y ser una secuencia ordenada, se preserva el orden. Si la secuencia
se vacı́a, también está ordenada.
Por H.I. tenemos que los primeros n elementos de C cumplen
c1 ≤ ⋯ ≤ cn
Si cn+1 fuera estrictamente menor a alguno de estos elementos, implicarı́a
una de las siguientes contradicciones
A o B no están ordenadas (ya probamos que lo están)
cn+1 es extraı́do en una iteración anterior por el criterio de selección
Luego, concluimos el resultado buscado
c1 ≤ ⋯ ≤ cn ≤ cn+1
18 / 35
Complejidad de memoria de Merge
La ejecución de ejemplo que mostramos
considera una nueva secuencia C donde se
insertan los valores
8
a 20 15 Para ∣A∣ + ∣B∣ = n necesitamos memoria
29 adicional O(n)
40
50 No necesita mover elementos dentro de
ninguna secuencia
60
70 También se puede realizar in place
82
Usar el mismo espacio reservado a A y
b 32 B: memoria adicional O(1)
41 Mover todos los datos mayores al
65 insertado
Impacta en la complejidad de tiempo...
19 / 35
Complejidad de tiempo de Merge
Consideramos la implementación sugerida mediante una secuencia adicional
El algoritmo tiene dos fases
1. Extracción desde ambas secuencias A y B
● Se decide quién extraer comparando los menores O(1)
● Se inserta el dato en C O(1)
● Esto se repite O(n) veces total O(n)
2. Reubicación de la secuencia no vacı́a restante
● Se saca un elemento de la restante O(1)
● Se inserta el dato en C O(1)
● Esto se repite O(n) veces total O(n)
Usando O(n) memoria adicional, Merge es O(n)
20 / 35
Complejidad de tiempo de Merge (in place)
Si consideramos usar el espacio reservado para A y B
El algoritmo tiene dos fases
1. Extracción desde ambas secuencias A y B
● Se decide quién extraer comparando los menores O(1)
● Se inserta el dato en al comienzo O(n)
● Esto se repite O(n) veces total O(n2 )
2. Reubicación de la secuencia no vacı́a restante: no necesario
● El resto de los elementos está en su posición correcta
Usando O(1) memoria adicional, Merge es O(n2 )
21 / 35
Complejidad de tiempo de Merge
Tenemos un algoritmo lineal para obtener una secuencia ordenada
Pero el requisito de las sub-secuencias ordenadas es demasiado exigente
¿Podemos usar Merge para ordenar una secuencia arbitraria?
Dada una secuencia arbitraria
Estamos listos si logramos crear dos sub-secuencias ordenadas a partir
de ella
Luego las combinamos con Merge
22 / 35
Sumario
Introducción
Merge
Merge Sort
Cierre
Dividir para conquistar
El plan para usar Merge en un algoritmo de ordenación sigue la estrategia
dividir para conquistar
La estrategia sigue los siguientes pasos
1. Dividir el problema original en dos (o más) sub-problemas del mismo
tipo
2. Resolver recursivamente cada sub-problema
3. Encontrar solución al problema original combinando las soluciones a
los sub-problemas
Los sub-problemas son instancias más pequeñas del problema a resolver
23 / 35
Dividir para conquistar y Merge
Podemos usar la estrategia dividir para conquistar en el problema de
ordenación, usando Merge
¿En qué parte del dividir para conquistar usaremos Merge?
La idea general para ordenar usando Mergedefine un nuevo algoritmo que
llamaremos MergeSort
1. Dividir la secuencia original en dos sub-secuencias
2. Llamamos recursivamente a MergeSort sobre las dos sub-secuencias
3. Combinamos las secuencias ordenadas resultantes mediante Merge
24 / 35
El algoritmo MergeSort
A continuación tenemos el pseudocódigo del algoritmo recursivo MergeSort
input : Secuencia A
output: Secuencia ordenada B
MergeSort (A):
1 if ∣A∣ = 1 : return A
2 Dividir A en mitades A1 y A2
3 B1 ← MergeSort(A1 )
4 B2 ← MergeSort(A2 )
5 B ← Merge(B1 , B2 )
6 return B
25 / 35
MergeSort: Ejemplo de ejecución
29 5 3 59 19 43 17 13 47 53 31 2 11 37 23 7
29 5 3 59 19 43 17 13 47 53 31 2 11 37 23 7
Dividir
29 5 3 59 19 43 17 13 47 53 31 2 11 37 23 7
29 5 3 59 19 43 17 13 47 53 31 2 11 37 23 7
29 5 3 59 19 43 17 13 47 53 31 2 11 37 23 7
5 29 3 59 19 43 13 17 47 53 2 31 11 37 7 23
Mezclar
3 5 29 59 13 17 19 43 2 31 47 53 7 11 23 37
3 5 13 17 19 29 43 59 2 7 11 23 31 37 47 53
2 3 5 7 11 13 17 19 23 29 31 37 43 47 53 59
26 / 35
Correctitud de MergeSort
Ejercicio (propuesto)
Demuestre que MergeSort es correcto
input : Secuencia A
output: Secuencia ordenada B
MergeSort (A):
1 if ∣A∣ = 1 : return A
2 Dividir A en mitades A1 y A2
3 B1 ← MergeSort(A1 )
4 B2 ← MergeSort(A2 )
5 B ← Merge(B1 , B2 )
6 return B
27 / 35
Carácter recursivo de MergeSort
Todo algoritmo recursivo debe
chequear primero el caso base
input : Secuencia A
output: Secuencia ordenada B Es el caso cuya solución no
MergeSort (A): requiere recursión
1 if ∣A∣ = 1 : return A En MergeSort: lı́nea 1
2 Dividir A en A1 y A2
3 B1 ← MergeSort(A1 ) Los llamados recursivos se hacen
4 B2 ← MergeSort(A2 ) sobre casos distintos al original
5 B ← Merge(B1 , B2 )
Se acercan un poco más al caso
6 return B
base
En MergeSort: lı́neas 3 y 4
28 / 35
Complejidad de MergeSort
Para el análisis de complejidad de tiempo, definimos
T (n) ∶= # pasos para ordenar n elementos
Con esto, consideramos los dos casos posibles al llamar a MergeSort
Si n = 1, aplica el caso base y solo
MergeSort (A): involucra un paso
1 if ∣A∣ = 1 : return A T (1) = 1
2 Dividir A en A1 y A2
3 B1 ← MergeSort(A1 )
4 B2 ← MergeSort(A2 ) Si n > 1, aplican los llamados
5 B ← Merge(B1 , B2 ) ● Dos llamados de tamaño n/2
6 return B ● Llamado a Merge
T (n) = 2T (n/2) + n
Este análisis aplica para toda secuencia de input:
Nos entregará el resultado de peor, mejor y caso promedio
29 / 35
Complejidad de MergeSort
La siguiente relación es una relación de recurrencia
n
T (1) = 1, T (n) = 2T ( ) + n
2
Podemos resolverla notando que la parte recursiva puede ser reescrita como
T (n) T (n/2)
T (n) = 2T (n/2) + n ⇔ = +1
n n/2
La gracia de esta expresión es que numeradores y denominadores incluyen la
misma fracción de n
Sin pérdida de generalidad, supondremos que n es potencia de 2
30 / 35
Complejidad de MergeSort
Construimos un sistema de ecuaciones reemplazando el argumento del lado
izquierdo por n, n/2, n/4, . . . , 2 de forma que el último término contiene
T (1) (nuestro caso base)
T (n) T (n/2)
ecuación 1 = +1
n n/2
T (n/2) T (n/4)
ecuación 2 = +1
n/2 n/4
...
T (2) T (1)
ecuación k = +1
2 1
Como el lado derecho de la i-ésima ecuación considera la potencia 2i , de la
k-ésima ecuación deducimos
n
1= ⇒ 2k = n ⇒ k = log(n)
2k
31 / 35
Complejidad de MergeSort
Sumamos las log(n) ecuaciones y simplificamos los términos que aparecen a
ambos lados
T (n) T (n/2)
ecuación 1 = +1
n n/2
T (n/2) T (n/4)
ecuación 2 = +1
n/2 n/4
...
T (2) T (1)
ecuación k = +1
2 1
T (n) T (1)
suma = + log(n)
n 1
Despejando, obtenemos T (n) = n log(n) + n
La complejidad de tiempo de MergeSort es O(n log(n))
32 / 35
Complejidad de MergeSort
En términos de memoria adicional
MergeSort (A): El caso base no ocupa memoria
1 if ∣A∣ = 1 : return A adicional
2 Dividir A en A1 y A2
3 B1 ← MergeSort(A1 ) Para ∣A∣ = n, la lı́nea 5 ocupa O(n)
4 B2 ← MergeSort(A2 )
Ojo! Los llamados recursivos no van
5 B ← Merge(B1 , B2 )
acumulando memoria reservada, por lo
6 return B
que no sumamos O(n) por llamado
La memoria adicional se puede reciclar:
La complejidad de memoria de MergeSort es O(n)
33 / 35
Complejidad de algoritmos de ordenación
Resumimos los resultados de complejidad por caso hasta el momento
Caso Memoria
Algoritmo Mejor caso Peor caso
promedio adicional
Selection Sort O(n2 ) O(n2 ) O(n2 ) O(1)
Insertion Sort O(n) O(n2 ) O(n2 ) O(1)
Merge Sort O(n log(n)) O(n log(n)) O(n log(n)) O(n)
Quick Sort ? ? ? ?
Heap Sort ? ? ? ?
Notemos la mejora en tiempo con MergeSort
a cambio de memoria adicional
34 / 35
Sumario
Introducción
Merge
Merge Sort
Cierre
Objetivos de la clase
Comprender el algoritmo Merge para combinar secuencias ordenadas
Determinar complejidad de Merge y el trade off de ejecutarlo in place
Demostrar correctitud de Merge
Comprender el uso de Merge como algoritmo de ordenación general en
MergeSort
Determinar la complejidad de MergeSort
35 / 35