Merge Sort
Splits the array in halves, sorts each one recursively and merges them.
- Level
- Advanced
- Topic:
- Sorting & searching
- Concepts:
- Input & output
- Arrays
- SubProcesos
- Recursion
- Mientras
- Para
- Si
- Randomness
Run, change and debug this example in your browser.
What you'll learn
OrdenarPorMezcla calls itself on each half until the pieces have one element, and Mezclar joins two sorted pieces by always taking the smaller of the two fronts. The array is halved about log n times and each level merges n elements: always O(n log n), at the price of a temporary array of size n. Arrays are passed by reference, so every subprocess works on the same array.
Code
// Muestra el arreglo completo solo si es corto (30 o menos)SubProceso MostrarDatos(titulo, datos, n) Definir i Como Entero Si n <= 30 Entonces Escribir Sin Saltar titulo Para i <- 1 Hasta n Hacer Escribir Sin Saltar datos[i], " " FinPara Escribir "" SiNo Escribir titulo, n, " números (el primero es ", datos[1], " y el último ", datos[n], ")" FinSiFinSubProceso// Une dos tramos ya ordenados: datos[izquierda..medio] y datos[medio+1..derecha]SubProceso Mezclar(datos, temporal, izquierda, medio, derecha) Definir i, j, k Como Entero i <- izquierda j <- medio + 1 k <- izquierda // Tomamos siempre el menor de los dos frentes Mientras i <= medio Y j <= derecha Hacer // Con <= los iguales conservan su orden: por eso es estable Si datos[i] <= datos[j] Entonces temporal[k] <- datos[i] i <- i + 1 SiNo temporal[k] <- datos[j] j <- j + 1 FinSi k <- k + 1 FinMientras // Copiamos lo que haya sobrado de cualquiera de las dos mitades Mientras i <= medio Hacer temporal[k] <- datos[i] i <- i + 1 k <- k + 1 FinMientras Mientras j <= derecha Hacer temporal[k] <- datos[j] j <- j + 1 k <- k + 1 FinMientras // Devolvemos el tramo mezclado al arreglo original Para k <- izquierda Hasta derecha Hacer datos[k] <- temporal[k] FinParaFinSubProceso// Los arreglos se pasan por referencia: el subproceso ordena el arreglo del algoritmoSubProceso OrdenarPorMezcla(datos, temporal, izquierda, derecha) Definir medio Como Entero // Un tramo de un solo elemento ya está ordenado: ahí termina la recursión Si izquierda < derecha Entonces medio <- Trunc((izquierda + derecha) / 2) OrdenarPorMezcla(datos, temporal, izquierda, medio) OrdenarPorMezcla(datos, temporal, medio + 1, derecha) Mezclar(datos, temporal, izquierda, medio, derecha) FinSiFinSubProcesoAlgoritmo OrdenamientoMezcla Definir datos, temporal, n, i Como Entero Escribir "¿Cuántos números quieres ordenar? (1 a 512)" Leer n // temporal es la memoria extra que necesita la mezcla Dimension datos[n], temporal[n] Para i <- 1 Hasta n Hacer datos[i] <- Aleatorio(1, 99) FinPara MostrarDatos("Antes: ", datos, n) OrdenarPorMezcla(datos, temporal, 1, n) MostrarDatos("Después: ", datos, n)FinAlgoritmoFlowchart
Each block in the flowchart matches one instruction in the code.
Sample run
This is what the program shows when it runs. The answers typed by the user are highlighted.
¿Cuántos números quieres ordenar? (1 a 512)User answer: 12Antes: 42 60 96 80 54 87 85 17 84 18 5 79 Después: 5 17 18 42 54 60 79 80 84 85 87 96
Complexity
How much work and memory it needs as the amount of data (n) grows.
| Case | Cost |
|---|---|
| Best | O(n log n) |
| Average | O(n log n) |
| Worst | O(n log n) |
| Memory | O(n) |
Traits:Stable
Challenge
Print every range that gets merged, with its left and right ends.
Show hint
Add an Escribir at the start of Mezclar; try a small n so there aren't too many lines.
Related examples
Heap Sort
Arranges the array as a heap, then takes the largest out again and again.
AdvancedBubble Sort
Sorts random numbers by swapping neighbors, and stops as soon as they're in order.
IntermediateInsertion Sort
Inserts each number among the sorted ones, like arranging cards in your hand.
Intermediate