Merge Sort
Última actualización
Merge sort es un algoritmo de divide y vencerás. Divide recursivamente el arreglo por la mitad hasta que cada pieza tiene un solo elemento (que está trivialmente ordenado), y luego fusiona las piezas de nuevo en orden. El paso de fusión recorre dos subarreglos ordenados con dos punteros, copiando siempre el elemento frontal más pequeño. Pulsa reproducir arriba para ver cómo se reconstruye el arreglo fusión a fusión.
Como siempre divide por la mitad, merge sort se ejecuta en tiempo O(n log n) en todos los casos: su peor caso es tan bueno como su mejor caso. La contrapartida es O(n) de espacio adicional para el búfer temporal de fusión.
Complejidad temporal y espacial
| Caso | Complejidad | Notas |
|---|---|---|
| Mejor caso | O(n log n) | Siempre divide la entrada a la mitad |
| Caso promedio | O(n log n) | Orden aleatorio |
| Peor caso | O(n log n) | Garantizado - no hay entradas malas |
| Espacio | O(n) | Búfer temporal para la fusión |
| Estable | Sí | Los empates se resuelven por la izquierda durante la fusión |
Paso a paso
| Paso | Qué ocurre |
|---|---|
| 1 | Si el rango tiene 0 o 1 elementos, ya está ordenado. |
| 2 | Divide el rango en dos mitades. |
| 3 | Ordena recursivamente la mitad izquierda con merge sort. |
| 4 | Ordena recursivamente la mitad derecha con merge sort. |
| 5 | Fusiona las dos mitades ordenadas con dos punteros. |
Ejemplo resuelto
Ordenando [5, 2, 4, 1]:
| Pasada | Arreglo | Acción |
|---|---|---|
| Dividir | [5, 2] | [4, 1] | Divide el arreglo en dos mitades |
| Dividir | [5] [2] | [4] [1] | Divide de nuevo hasta que cada pieza es un solo elemento |
| Fusionar | [2, 5] | [1, 4] | Fusiona [5],[2] en [2, 5] y [4],[1] en [1, 4] |
| Fusionar | [1, 2, 4, 5] | Fusiona [2, 5] y [1, 4]: elige 1, luego 2, luego 4, luego 5 |
| Listo | [1, 2, 4, 5] | El arreglo está completamente ordenado |
Cuándo usar merge sort
| Úsalo cuando | Evítalo cuando |
|---|---|
Necesitas un peor caso garantizado de O(n log n) | La memoria es escasa y O(n) de espacio extra es inaceptable |
| La estabilidad importa (las claves iguales mantienen su orden) | Ordenas arreglos pequeños donde insertion sort es más rápido |
| Ordenas una lista enlazada | El ordenamiento in situ es un requisito estricto |
| Los datos son demasiado grandes para la RAM (ordenamiento externo) | La localidad de caché domina y las pasadas in situ de quicksort ganan |
Código de Merge Sort
Una implementación limpia y ejecutable de Merge Sort en Python, JavaScript, Java, C++, C. Elige un lenguaje, copia el código o ábrelo ya cargado en el Playground de Coddy.
Código de Merge Sort en Python
Python
1def merge_sort(a):2 if len(a) <= 1:3 return a4 mid = len(a) // 25 left = merge_sort(a[:mid])6 right = merge_sort(a[mid:])7 return merge(left, right)8
9
10def merge(left, right):11 out = []12 i = j = 013 while i < len(left) and j < len(right):14 if left[i] <= right[j]:15 out.append(left[i])16 i += 117 else:18 out.append(right[j])19 j += 120 out.extend(left[i:])21 out.extend(right[j:])22 return out23
24
25nums = [38, 27, 43, 3, 9, 82, 10]26print("Before:", nums)27print("After: ", merge_sort(nums))Código de Merge Sort en JavaScript
JavaScript
1function mergeSort(arr) {2 if (arr.length <= 1) return arr;3 const mid = Math.floor(arr.length / 2);4 const left = mergeSort(arr.slice(0, mid));5 const right = mergeSort(arr.slice(mid));6 return merge(left, right);7}8
9// Merge two sorted arrays into one sorted array10function merge(left, right) {11 const out = [];12 let i = 0;13 let j = 0;14 while (i < left.length && j < right.length) {15 out.push(left[i] <= right[j] ? left[i++] : right[j++]);16 }17 return out.concat(left.slice(i), right.slice(j));18}19
20const data = [5, 2, 9, 1, 7, 3];21console.log("Before:", data);22console.log("Sorted:", mergeSort(data));Código de Merge Sort en Java
Java
1import java.util.Arrays;2
3public class Main {4 static void mergeSort(int[] arr, int left, int right) {5 if (left >= right) return;6 int mid = (left + right) / 2;7 mergeSort(arr, left, mid);8 mergeSort(arr, mid + 1, right);9 merge(arr, left, mid, right);10 }11
12 // Merge two sorted halves into a temp array, then copy back13 static void merge(int[] arr, int left, int mid, int right) {14 int[] tmp = new int[right - left + 1];15 int i = left, j = mid + 1, k = 0;16 while (i <= mid && j <= right) {17 tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];18 }19 while (i <= mid) tmp[k++] = arr[i++];20 while (j <= right) tmp[k++] = arr[j++];21 System.arraycopy(tmp, 0, arr, left, tmp.length);22 }23
24 public static void main(String[] args) {25 int[] arr = {38, 27, 43, 3, 9, 82, 10};26 System.out.println("Before: " + Arrays.toString(arr));27 mergeSort(arr, 0, arr.length - 1);28 System.out.println("After: " + Arrays.toString(arr));29 }30}Código de Merge Sort en C++
C++
1#include <iostream>2#include <vector>3
4void printVec(const std::vector<int>& a) {5 for (int x : a) std::cout << x << " ";6 std::cout << "\n";7}8
9void merge(std::vector<int>& a, int lo, int mid, int hi) {10 std::vector<int> tmp;11 tmp.reserve(hi - lo + 1);12 int i = lo, j = mid + 1;13 while (i <= mid && j <= hi) {14 if (a[i] <= a[j]) tmp.push_back(a[i++]);15 else tmp.push_back(a[j++]);16 }17 while (i <= mid) tmp.push_back(a[i++]);18 while (j <= hi) tmp.push_back(a[j++]);19 for (size_t k = 0; k < tmp.size(); ++k) a[lo + k] = tmp[k];20}21
22void mergeSort(std::vector<int>& a, int lo, int hi) {23 if (lo >= hi) return;24 int mid = lo + (hi - lo) / 2;25 mergeSort(a, lo, mid); // sort the left half26 mergeSort(a, mid + 1, hi); // sort the right half27 merge(a, lo, mid, hi); // merge the sorted halves28}29
30int main() {31 std::vector<int> data = {38, 27, 43, 3, 9, 82, 10};32 std::cout << "Before: ";33 printVec(data);34 mergeSort(data, 0, static_cast<int>(data.size()) - 1);35 std::cout << "After: ";36 printVec(data);37 return 0;38}Código de Merge Sort en C
C
1#include <stdio.h>2#include <stdlib.h>3
4void printArr(const int a[], int n) {5 for (int i = 0; i < n; i++) printf("%d ", a[i]);6 printf("\n");7}8
9void merge(int a[], int lo, int mid, int hi) {10 int* tmp = malloc((hi - lo + 1) * sizeof(int));11 int i = lo, j = mid + 1, k = 0;12 while (i <= mid && j <= hi) {13 if (a[i] <= a[j]) tmp[k++] = a[i++];14 else tmp[k++] = a[j++];15 }16 while (i <= mid) tmp[k++] = a[i++];17 while (j <= hi) tmp[k++] = a[j++];18 for (k = 0; k <= hi - lo; k++) a[lo + k] = tmp[k];19 free(tmp);20}21
22void mergeSort(int a[], int lo, int hi) {23 if (lo >= hi) return;24 int mid = lo + (hi - lo) / 2;25 mergeSort(a, lo, mid); // sort the left half26 mergeSort(a, mid + 1, hi); // sort the right half27 merge(a, lo, mid, hi); // merge the sorted halves28}29
30int main(void) {31 int data[] = {38, 27, 43, 3, 9, 82, 10};32 int n = sizeof(data) / sizeof(data[0]);33 printf("Before: ");34 printArr(data, n);35 mergeSort(data, 0, n - 1);36 printf("After: ");37 printArr(data, n);38 return 0;39}Preguntas frecuentes sobre Merge Sort
¿Cuál es la complejidad temporal de merge sort?
Merge sort es
O(n log n) en el mejor, el promedio y el peor caso, porque siempre divide el arreglo por la mitad. Usa O(n) de espacio adicional para el búfer de fusión.¿Es merge sort estable?
Sí, cuando el paso de fusión resuelve los empates tomando primero de la mitad izquierda. Esto mantiene los elementos iguales en su orden relativo original, por lo que merge sort es una opción común para el ordenamiento estable.
¿Por qué usar merge sort en lugar de quicksort?
Merge sort garantiza
O(n log n) incluso en entradas adversas y es estable, mientras que quicksort puede degradarse a O(n²). Merge sort también se prefiere para listas enlazadas y ordenamiento externo. La desventaja es su memoria adicional de O(n).¿Cuál es la diferencia entre merge sort y quicksort?
Ambos son ordenamientos de divide y vencerás, pero quicksort particiona en torno a un pivote y ordena in situ con
O(log n) de espacio de pila, mientras que merge sort divide a ciegas por la mitad y fusiona usando un búfer de O(n). Quicksort suele ser más rápido en la práctica por la localidad de caché, pero merge sort tiene un peor caso garantizado de O(n log n) y es estable.¿Cuándo debería usar merge sort en la práctica?
Recurre a merge sort cuando necesitas un ordenamiento estable con una cota garantizada de
O(n log n), al ordenar listas enlazadas (donde no necesita acceso aleatorio), o al hacer ordenamiento externo de datos demasiado grandes para caber en memoria. Evítalo cuando la memoria es escasa, ya que necesita O(n) de espacio adicional.¿Merge sort ordena in situ?
No. El merge sort estándar reserva un búfer temporal de
O(n) para fusionar las dos mitades, por lo que no es in situ. Existen variantes de fusión in situ, pero son complejas y o bien más lentas o pierden la estabilidad, así que la versión basada en búfer es la opción común.Recursos relacionados
Más visualizaciones
