Algoritmos

Algoritmos de ordenamiento: cuáles son, cómo funcionan y cuál elegir

Un algoritmo de ordenamiento pone una lista en un orden fijado, por ejemplo de menor a mayor. Los más conocidos son burbuja, selección, inserción, merge sort, quicksort y heapsort. Se escogen por cuánto tardan, cuánta memoria extra piden y si respetan el orden de los empates. En la práctica suele convenir el que ya trae el lenguaje.

Por Jhon Mosquera17 nov 202613 min de lectura

Última actualización: 2026-11-17

Contenido de esta página

Tim Peters tenía un problema raro: el ordenamiento que iba a reemplazar ya era rápido. Python usaba entonces un híbrido muy afinado llamado samplesort. En listas al azar, su sustituto no prometía ganarle: según el propio Peters, podía salir más rápido o más lento, dependiendo de la máquina [2].

Aun así lo cambió. La versión 2.3 de Python, publicada el 29 de julio de 2003, estrenó el método de ordenar listas reescrito a fondo por Peters, y bastante más rápido [1]. Él lo bautizó, con humor, timsort [2].

La razón está en su documento técnico, que todavía acompaña el código de Python. Ahí escribió: «creo que las listas muy a menudo tienen, en la vida real, un orden parcial aprovechable» (traducción propia) [2]. Peters no apostó por el peor caso de los libros. Apostó por la forma en que llegan los datos de verdad: por tandas, casi en orden, con unos pocos fuera de sitio. En listas con orden previo, su método superaba con holgura al anterior [2].

Esa apuesta es el centro de este tema. Ordenar parece un problema resuelto. Lo que no tiene una respuesta única es qué método conviene. Depende de cómo vienen los datos, de cuánta memoria hay y de si importa el orden de los empates.

Lápices de colores ordenados del celeste al azul marino en una lata, junto a lápices sueltos sin ordenar

¿Qué es un algoritmo de ordenamiento?

Un algoritmo de ordenamiento es un procedimiento que pone los elementos de una lista en un orden fijado de antemano, como de menor a mayor o en orden alfabético [3]. El resultado tiene los mismos elementos que la entrada, solo que reacomodados. Los apuntes del curso de algoritmos del MIT, el Instituto Tecnológico de Massachusetts, lo llaman una permutación ordenada: los mismos datos, en otro orden, y ese orden es el correcto [4].

Hay docenas de métodos. El diccionario de algoritmos del NIST, el instituto de estándares de Estados Unidos, dice que la elección depende de varias cosas [3]. Cuenta cuántos elementos hay frente a la memoria disponible y qué tan ordenados vienen. También pesa el rango de valores y cuánto cuesta comparar dos elementos frente a cuánto cuesta moverlos [3].

Si quiere repasar qué convierte una lista de pasos en un algoritmo, está la guía de qué es un algoritmo. Y el mapa completo del tema, con el orden en que conviene estudiarlo, está en la guía de estructuras de datos y algoritmos.

¿Qué son la clave y el criterio de comparación?

Para ordenar hay que decidir dos cosas. La clave es el dato por el que se ordena: la fecha de una factura, el apellido de un estudiante, el recaudo de un municipio. El criterio de comparación es la regla que dice cuál de dos claves va primero: de menor a mayor, en orden alfabético, de la más reciente a la más antigua.

La guía de ordenamiento de Python lo resuelve con un parámetro llamado key. Es una función que se aplica a cada elemento antes de comparar, y entrega el valor por el que se va a ordenar [6]. Piense, como ejemplo ilustrativo, en la oficina de rentas de un municipio. Su listado de contribuyentes se puede ordenar por cédula, por barrio o por valor pagado sin tocar los datos: solo cambia la clave.

¿Qué es un ordenamiento estable?

Un ordenamiento es estable cuando los elementos con la misma clave salen en el mismo orden en que entraron [5]. Parece un detalle. No lo es.

Un caso ilustrativo. Una ferretería de Bucaramanga tiene los pedidos del día en orden de llegada. El primero y el tercero van para Girón. Si se ordenan por municipio de entrega con un método estable, dentro de Girón el primero sigue antes que el tercero. Con uno que no es estable, pueden quedar al revés, y el repartidor sale con la ruta cambiada.

Sedgewick y Wayne, autores del libro Algorithms de la Universidad de Princeton, usan el mismo tipo de ejemplo: transacciones guardadas por hora que luego se separan por ciudad [7]. Si el método no es estable, las de cada ciudad pueden perder su orden de hora [7]. Python, por su parte, garantiza que sus ordenamientos son estables [6].

¿Qué significa ordenar «en el lugar»?

Ordenar en el lugar (in-place, en inglés) es reacomodar los elementos dentro del mismo espacio donde estaban, sin copiar la lista a otra parte [8]. El problema es que las fuentes no ponen el límite en el mismo sitio, y conviene saberlo antes de leer cualquier tabla.

FuenteQué exige para llamar «en el lugar» a un método
Apuntes del MIT [4]Memoria extra constante, es decir, que no crezca con la cantidad de datos
Diccionario del NIST [8]Los datos ordenados ocupan el mismo espacio; admite algo de memoria de control que crece más despacio que la lista, con un número fijo de elementos guardados aparte a la vez
Sedgewick y Wayne [9]Ninguna memoria extra, salvo quizá una pila pequeña de llamadas a funciones o unas pocas variables

Por eso «en el lugar» y «memoria constante» no son sinónimos aquí. Con la vara del MIT, un método que necesite una pila de llamadas que crece con los datos ya no cuenta como en el lugar. Con la del libro de Princeton, sí. La tabla de la sección siguiente usa la marca del libro y, aparte, dice qué memoria pide cada método.

¿Cuáles son los algoritmos de ordenamiento y su complejidad?

Los seis métodos clásicos se dividen por cuánto trabajo hacen y cuánta memoria piden. La tabla cuenta comparaciones, es decir, cuántas veces el método pregunta cuál de dos elementos va primero. Las cifras son de la tabla de Sedgewick y Wayne y valen para las implementaciones de su libro: incluyen las constantes y dejan por fuera los términos pequeños [10].

En la tabla, n es la cantidad de elementos. El símbolo log₂ n es el número de veces que hay que partir n por la mitad hasta llegar a uno, y ln n es el logaritmo natural. Medir el costo de un algoritmo a fondo es un tema propio, el de la complejidad algorítmica; aquí basta con leer cómo crecen las cifras.

AlgoritmoMejor casoCaso promedioPeor casoMemoria extra¿Estable?¿En el lugar?Cuándo usarlo
Burbujan½ n²½ n²Unas pocas variables [9]SíSíRara vez: el libro lo considera superado por inserción [10]
Selección½ n²½ n²½ n²Unas pocas variables [9]NoSíSi mover un elemento cuesta mucho más que compararlo: hace solo n intercambios [10]
Inserciónn¼ n²½ n²Unas pocas variables [9]SíSíListas pequeñas o casi ordenadas [10]
Merge sort½ n log₂ nn log₂ nn log₂ nProporcional a n: un arreglo auxiliar del tamaño de la lista [11]SíNoCuando importa la estabilidad y hay memoria disponible: puede ser la mejor opción [7]
Quicksortn log₂ n2 n ln n½ n²Una pila pequeña de llamadas [12]NoSíUso general: el libro lo da como el más rápido en la práctica [10]
Heapsortn (ver nota)2 n log₂ n2 n log₂ nNinguna aparte de la lista [13]NoSíCuando se necesita garantía de n log n sin memoria extra [10]

Nota: el libro da n como mejor caso de heapsort y aclara que es n log₂ n si todas las claves son distintas [10]. Las marcas de estable y en el lugar también son las del libro [10]. El NIST clasifica igualmente como métodos en el lugar a burbuja, selección, quicksort y heapsort, y a burbuja como estable [14][15][18][19].

En una frase cada uno, según el diccionario del NIST:

  • Burbuja compara cada par de vecinos, los intercambia si están al revés y repite la pasada hasta que no haya cambios [14].
  • Selección busca el menor de los que faltan y lo lleva a su posición final, una y otra vez [15].
  • Inserción toma el siguiente elemento y lo mete en su sitio entre los que ya quedaron ordenados [16].
  • Merge sort (ordenamiento por mezcla) parte la lista en dos, ordena cada mitad aplicándose a sí mismo y luego mezcla las dos mitades en una sola [17].
  • Quicksort escoge un pivote (un elemento de referencia), separa los mayores de los menores y repite lo mismo en cada grupo [18].
  • Heapsort arma un montículo, un árbol que deja siempre arriba el valor mayor (o, en la otra versión, el menor), y saca ese mayor una y otra vez [19].

El NIST da los costos en notación O, una forma de decir cómo crece el trabajo cuando crecen los datos, sin fijarse en los detalles. Selección cuesta Θ(n²), un símbolo que indica que el costo crece justo a ese ritmo, e inserción, O(n²) por los movimientos [15][16]. Merge sort cuesta Θ(n log n) y heapsort, O(n log n) [17][19].

Quicksort puede llegar a Θ(n²) en el peor caso, pero lo típico es O(n log n) [18]. Burbuja es O(n²) con datos cualesquiera y se acerca a Θ(n) si la lista ya venía casi en orden [14]. Cada método tendrá su propia explicación paso a paso; el ordenamiento burbuja, merge sort y quicksort son los primeros de esa lista. El montículo está explicado en la guía de estructuras de datos.

¿Qué diferencia hay entre los métodos de ordenamiento simples y los eficientes?

Los métodos simples, burbuja, selección e inserción, hacen un trabajo que crece con el cuadrado de los datos. Los eficientes, merge sort, quicksort y heapsort, crecen más o menos como n log n. Con pocos datos da igual. Con muchos, la diferencia se vuelve enorme.

Un cálculo propio con las fórmulas de la tabla lo muestra. Para ordenar 10.000 facturas, selección haría unos 50 millones de comparaciones [10]. Merge sort, en su caso promedio, haría unas 132.877 [10]. Es una diferencia de unas 376 veces, y crece con cada factura nueva.

Pero los simples no sobran, y la razón es la misma apuesta de Peters. Una inversión es un par de elementos que están al revés entre sí. Sedgewick y Wayne muestran que inserción hace exactamente tantos intercambios como inversiones tenga la lista [9]. Si la lista ya está casi en orden, quedan pocas inversiones y el trabajo es casi lineal [9].

Por eso los métodos eficientes suelen llevar uno simple adentro. Pasar a inserción cuando los pedazos son pequeños mejora entre un 10 y un 15 % el tiempo de un merge sort típico, según el libro de Princeton [11]. En quicksort, el mismo libro dice que cualquier corte entre 5 y 15 elementos probablemente funcione bien en la mayoría de los casos, aunque el óptimo depende del sistema [12].

¿Qué es el ordenamiento interno y el externo?

Un ordenamiento interno usa solo la memoria principal del computador, la memoria RAM, y supone que puede llegar rápido a cualquier dato [20]. Uno externo usa además memoria externa, como un disco, durante el proceso [21]. La diferencia aparece cuando los datos no caben en la memoria principal: la mayoría de los métodos comunes suponen acceso rápido a todo, y entonces dejan de servir [21].

El NIST agrega una advertencia práctica. La memoria virtual, el truco del sistema operativo que usa el disco como si fuera RAM, puede esconder el problema. Aun así, con datos mucho más grandes que la memoria, un ordenamiento externo diseñado para eso puede ser mucho más rápido [21]. En la lista de variantes externas del NIST dominan las que trabajan por mezcla: cinco de siete [21]. Es la idea de merge sort llevada al disco: ordenar pedazos que sí caben y luego mezclarlos.

En el ordenamiento de datos que hace un gestor de bases de datos, ese cambio ocurre solo. En PostgreSQL, el parámetro work_mem fija cuánta memoria puede usar una operación de ordenamiento antes de escribir en archivos temporales del disco; por defecto son 4 megabytes [22]. Y el plan de ejecución que muestra el gestor dice si un ordenamiento se hizo en memoria o en disco [23].

Cómo se pide ese orden dentro de una consulta es tema de SQL, el lenguaje para consultar bases de datos, que lo hace con la instrucción ORDER BY (ordenar por). Ordenar una hoja de cálculo es asunto de Excel, y ordenar una tabla en Python, de pandas.

¿Por qué en la práctica se usa el ordenamiento de la librería estándar?

Porque los ordenamientos que traen los lenguajes son híbridos afinados y probados durante años, y los casos raros ya están cubiertos. Una librería es código ya escrito que viene con el lenguaje. La de Python usa Timsort [2]; la de C++ que acompaña a GCC, el compilador del proyecto GNU, usa introsort [25]. Ninguno de los dos es uno de los seis de la tabla: son mezclas de varios.

¿Cómo funciona Timsort, el ordenamiento de Python?

Peters lo describe como un merge sort adaptativo, estable y natural [2]. Natural quiere decir que no parte la lista a ciegas. Primero recorre la lista y detecta tramos que ya están en orden, que él llama runs; si un tramo viene al revés, lo voltea [2]. Si un tramo es muy corto, lo alarga con una versión de inserción, y después mezcla los tramos entre sí [2].

El costo de la estabilidad es memoria. Timsort puede necesitar un arreglo temporal de hasta la mitad de n referencias, sobre todo con datos al azar. Con datos que ya traen estructura, a veces no necesita memoria extra [2]. A cambio, en listas con orden previo puede hacer muy pocas comparaciones: tan pocas como n − 1 [2].

Es el método con que Python ordena sus listas desde la versión 2.3 [1][2]. La guía oficial de ordenamiento añade un uso práctico: como Timsort aprovecha el orden que ya existe, ordenar en varias pasadas es eficiente [6].

¿Qué es introsort y quién lo usa?

Introsort es un quicksort que se pasa a heapsort cuando detecta un caso patológico, es decir, cuando el tiempo empieza a crecer con el cuadrado de los datos [24]. El NIST lo relaciona con un artículo de David Musser de 1997 [24]. La idea junta lo mejor de dos filas de la tabla: la rapidez típica de quicksort y la garantía de heapsort.

La biblioteca estándar de C++ que distribuye GCC lo implementa así. Su función de ordenamiento corre un quicksort con un límite de profundidad igual a dos veces el logaritmo en base 2 de n [25]. Si se agota ese límite, termina el tramo con un ordenamiento de montículo. Deja sin tocar los pedazos de 16 elementos o menos y los remata al final con inserción [25]. Es una elección de esa implementación: otras bibliotecas de C++ pueden resolverlo distinto.

¿Por qué tanta precaución? Sedgewick y Wayne cuentan que con una técnica que describió M. D. McIlroy, se pueden construir entradas que hacen correr en tiempo cuadrático el ordenamiento de tipos primitivos de Java 6, una variante de quicksort. Peor aún, desbordan la pila de llamadas [12]. Un quicksort casero no tiene ninguna defensa contra eso. El mismo libro anota que la librería de Java usa quicksort para los tipos primitivos, como los números, y merge sort para los objetos [7]. Así cambia velocidad y memoria por estabilidad y rendimiento garantizado [7].

¿Cuánto se nota el caso casi ordenado? Una medición propia

Para ver la apuesta de Peters con números, escribí un programa corto que cuenta cuántas comparaciones hace sorted(). Lo probé con tres listas de 100.000 números: una ya ordenada, una casi ordenada con diez intercambios al azar y una revuelta.

import random
import sys
import time

# Envoltorio que cuenta cuántas veces sorted() compara dos elementos
class Contado:
    comparaciones = 0
    def __init__(self, valor):
        self.valor = valor
    def __lt__(self, otro):
        Contado.comparaciones += 1
        return self.valor < otro.valor

def medir(nombre, datos):
    Contado.comparaciones = 0
    envueltos = [Contado(x) for x in datos]
    inicio = time.perf_counter()
    sorted(envueltos)
    segundos = time.perf_counter() - inicio
    cuenta = f"{Contado.comparaciones:,}".replace(",", ".")
    print(f"{nombre:<14} {cuenta:>9} comparaciones  {segundos * 1000:6.0f} ms")

n = 100_000
random.seed(2026)                    # semilla fija: el conteo se repite igual
ordenada = list(range(n))
casi = ordenada.copy()
for _ in range(10):                  # diez intercambios al azar
    i, j = random.randrange(n), random.randrange(n)
    casi[i], casi[j] = casi[j], casi[i]
aleatoria = ordenada.copy()
random.shuffle(aleatoria)

print(f"Python {sys.version.split()[0]} · n = {n}")
medir("ya ordenada", ordenada)
medir("casi ordenada", casi)
medir("aleatoria", aleatoria)

Esta fue la salida en mi computador:

Python 3.11.15 · n = 100000
ya ordenada       99.999 comparaciones      40 ms
casi ordenada    101.074 comparaciones      65 ms
aleatoria      1.528.914 comparaciones   1928 ms

La lista ya ordenada costó 99.999 comparaciones, justo n − 1, el mínimo que anuncia el documento de Peters [2]. La casi ordenada costó apenas un poco más. La revuelta pidió unas quince veces más comparaciones que la ordenada.

Es una medición local y no se generaliza. Los milisegundos cambian de una corrida a otra y de un equipo a otro. Las comparaciones de la lista casi ordenada y de la revuelta dependen de la semilla que fijé, que es arbitraria, y de la versión de Python. Solo la de la lista ya ordenada es siempre n − 1.

¿Cómo elegir un algoritmo de ordenamiento?

Esta es mi regla de bolsillo. Es un criterio de oficio, no una ley, y cada punto se apoya en lo que ya vimos:

  1. Si el lenguaje trae su ordenamiento, úselo. En Python, sorted() o list.sort(); en C++, la función de su biblioteca estándar. Ya resuelven los casos raros [2][25].
  2. Si los datos vienen casi en orden y son pocos, inserción. Hace tan pocos intercambios como inversiones haya [9]. Si los datos son muchos, Timsort aprovecha ese orden por usted [2].
  3. Si necesita estabilidad, merge sort o Timsort. Es el caso de ordenar por varias columnas o de conservar el orden de llegada [6][7].
  4. Si necesita una garantía de peor caso sin memoria extra, heapsort [10].
  5. Si ordena números sueltos y la estabilidad no importa, un quicksort bien implementado. Una versión bien afinada le gana en la práctica a la mayoría de métodos [18].
  6. Si los datos no caben en la memoria, un ordenamiento externo por mezcla [21].
  7. Burbuja y selección, para aprender. Selección tiene un nicho: cuando mover un elemento cuesta mucho más que compararlo [10].

Vuelva a la oficina de rentas de un municipio, con su listado de contribuyentes ordenado por cédula que alguien quiere ver por barrio. Nadie ahí va a escribir un quicksort, y no debería. Lo que sí tiene que saber es que el orden por cédula dentro de cada barrio sobrevive solo si el método es estable. Esa pregunta, no la del algoritmo más rápido, es la que cambia el resultado que llega al escritorio del secretario de Hacienda.

Preguntas frecuentes

¿Cuál es el algoritmo de ordenamiento más rápido?

No hay uno que gane siempre. Para uso general, el libro de Sedgewick y Wayne pone a quicksort como el más rápido y dice que en la mayoría de situaciones prácticas es el método preferido [7]. Pero con datos que ya traen orden, un método adaptativo como Timsort puede terminar en n − 1 comparaciones [2]; el mejor caso del quicksort del libro es n log₂ n [10].

¿Qué algoritmo de ordenamiento usa Python?

Usa Timsort desde Python 2.3, la versión de julio de 2003 en la que Tim Peters reescribió el ordenamiento de listas [1][2]. Para ordenar ofrece dos vías: la función «sorted()», que crea una lista nueva, y el método «list.sort()», que modifica la lista original [6]. La documentación garantiza que sus ordenamientos son estables [6].

¿Se puede volver estable un ordenamiento que no lo es?

Sí. El NIST explica que basta con pegarle a cada clave la posición original del elemento [3]. Cuando dos claves empatan, la posición desempata y el orden de entrada se mantiene [3]. El costo es guardar un dato más por elemento.

¿Qué tipos de algoritmos de ordenamiento existen?

Se agrupan según el criterio que se mire. Por costo, hay métodos cuadráticos y métodos que crecen como n log n [10]. Por memoria, hay internos y externos [20][21], y métodos en el lugar o con memoria auxiliar [8]. El NIST describe además los ordenamientos por distribución, que reparten los elementos en estructuras intermedias y luego los juntan, como el radix o el de cubetas [26].

¿Vale la pena programar mi propio algoritmo de ordenamiento?

Para aprender, sí: escribir inserción o merge sort enseña mucho sobre costo y memoria. Para un sistema que va a producción, casi nunca. Las librerías ya traen defensas contra entradas diseñadas para volver lento un quicksort, como las que, con la técnica de McIlroy, hacen caer el ordenamiento de Java 6 [12].

Referencias

  1. Python Software Foundation. What’s New in Python 2.3, documentación oficial de Python — Python 2.3 se publicó el 29 de julio de 2003; el método sort() de las listas fue reescrito a fondo por Tim Peters y la implementación es bastante más rápida. Python docs: What’s New in Python 2.3 — Consultada: 2026-11-17.
  2. Tim Peters, repositorio oficial de CPython. Objects/listsort.txt — timsort como «an adaptive, stable, natural mergesort»; nombre «modestly called timsort»; tan pocas como N-1 comparaciones en arreglos parcialmente ordenados; en arreglos al azar puede ser más rápido o más lento que samplesort según la plataforma; arreglo temporal de hasta N//2 punteros; «I believe that lists very often do have exploitable partial order in real life»; detección de runs ascendentes y descendentes (estos se invierten); runs cortos alargados a minrun con «a stable binary insertion sort». CPython: Objects/listsort.txt — Consultada: 2026-11-17.
  3. NIST, Dictionary of Algorithms and Data Structures (Paul E. Black, ed.). Entrada sort (modificada el 2 de noviembre de 2020) — «Arrange items in a predetermined order»; hay docenas de algoritmos y la elección depende del número de elementos frente a la memoria de trabajo, del orden previo o del rango de las claves y del costo de comparar frente al de mover; cualquier ordenamiento se vuelve estable añadiendo la posición original a la clave. NIST DADS: sort — Consultada: 2026-11-17.
  4. MIT OpenCourseWare. Erik Demaine, Jason Ku y Justin Solomon, 6.006 Introduction to Algorithms, Lecture 3: Sorting (primavera de 2020) — la salida es una permutación ordenada de la entrada; «A sort is in place if it uses O(1) extra space». MIT OCW 6.006: Lecture 3, Sorting — Consultada: 2026-11-17.
  5. NIST, Dictionary of Algorithms and Data Structures (Paul E. Black, ed.). Entrada stable (modificada el 17 de diciembre de 2004) — algoritmo en el que el orden relativo de entrada de los elementos con claves iguales siempre se conserva en la salida. NIST DADS: stable — Consultada: 2026-11-17.
  6. Python Software Foundation. Sorting Techniques, documentación de Python 3.15.2 — list.sort() modifica la lista y sorted() construye una nueva; el parámetro key es una función que se llama sobre cada elemento antes de comparar; «Sorts are guaranteed to be stable»; Timsort hace eficientes los ordenamientos en varias pasadas porque aprovecha el orden ya presente. Python docs: Sorting Techniques — Consultada: 2026-11-17.
  7. Robert Sedgewick y Kevin Wayne, Princeton University. Algorithms, 4th Edition, sección 2.5 Sorting Applications — estabilidad con el ejemplo de transacciones ordenadas por hora y separadas por ciudad; inserción y mergesort son estables, selección, shellsort, quicksort y heapsort no; «In most practical situations, quicksort is the method of choice»; si la estabilidad importa y hay espacio, mergesort puede ser lo mejor; en Java, quicksort para tipos primitivos y mergesort para tipos de referencia. Princeton algs4: Sorting Applications — Consultada: 2026-11-17.
  8. NIST, Dictionary of Algorithms and Data Structures (Paul E. Black, ed.). Entrada in-place sort (Paul E. Black y Conrado Martínez; modificada el 15 de marzo de 2004) — los elementos ordenados ocupan el mismo almacenamiento que los originales; puede usar memoria adicional o(n) para control, pero a lo sumo un número constante de elementos en memoria auxiliar a la vez. NIST DADS: in-place sort — Consultada: 2026-11-17.
  9. Robert Sedgewick y Kevin Wayne, Princeton University. Algorithms, 4th Edition, sección 2.1 Elementary Sorts — los métodos en el lugar no usan memoria extra salvo quizá una pila pequeña de llamadas o un número constante de variables; el número de intercambios de inserción es igual al número de inversiones; definición de arreglo parcialmente ordenado. Princeton algs4: Elementary Sorts — Consultada: 2026-11-17.
  10. Robert Sedgewick y Kevin Wayne, Princeton University. Algorithms and Data Structures Cheatsheet, sitio del libro Algorithms, 4.ª edición — número de comparaciones «as implemented in this textbook», con constantes y sin términos de orden menor, marcas de en el lugar y estable, y observaciones: selección (½ n² en los tres casos; n intercambios), inserción (n, ¼ n², ½ n²; para arreglos pequeños o parcialmente ordenados), burbuja (n, ½ n², ½ n²; «rarely useful; dominated by insertion sort»), mergesort (½ n log₂ n, n log₂ n, n log₂ n; garantía n log n; estable), quicksort (n log₂ n, 2 n ln n, ½ n²; «fastest in practice»), heapsort (n, con n log₂ n si todas las claves son distintas; 2 n log₂ n; 2 n log₂ n; garantía n log n; en el lugar). Princeton algs4: Cheatsheet — Consultada: 2026-11-17.
  11. Robert Sedgewick y Kevin Wayne, Princeton University. Algorithms, 4th Edition, sección 2.2 Mergesort — garantiza N log N para cualquier entrada; su principal desventaja es que usa espacio extra proporcional a N (un arreglo auxiliar); pasar a inserción en subarreglos pequeños mejora entre 10 y 15 por ciento un mergesort típico. Princeton algs4: Mergesort — Consultada: 2026-11-17.
  12. Robert Sedgewick y Kevin Wayne, Princeton University. Algorithms, 4th Edition, sección 2.3 Quicksort — en el lugar «(uses only a small auxiliary stack)»; corte a inserción con cualquier valor entre 5 y 15, óptimo dependiente del sistema; la técnica de M. D. McIlroy construye entradas que hacen cuadrático el ordenamiento del sistema y desbordan la pila de llamadas, con ejemplos contra la librería de Java 6. Princeton algs4: Quicksort — Consultada: 2026-11-17.
  13. Robert Sedgewick y Kevin Wayne, Princeton University. Algorithms, 4th Edition, sección 2.4 Priority Queues — heapsort ordena sin necesitar espacio extra, manteniendo el montículo dentro del arreglo que se ordena. Princeton algs4: Priority Queues — Consultada: 2026-11-17.
  14. NIST, Dictionary of Algorithms and Data Structures (Paul E. Black, ed.). Entrada bubble sort (modificada el 7 de abril de 2023) — compara cada par adyacente, intercambia si hace falta y repite hasta que no haya intercambios; es in-place y estable; O(n²) con datos arbitrarios, se acerca a Θ(n) si la lista está casi en orden al comienzo. NIST DADS: bubble sort — Consultada: 2026-11-17.
  15. NIST, Dictionary of Algorithms and Data Structures (Paul E. Black, ed.). Entrada selection sort (modificada el 21 de abril de 2022) — busca el menor de los restantes y lo mueve a su posición final; Θ(n²); O(n) intercambios; la implementación en el lugar por intercambio no es estable. NIST DADS: selection sort — Consultada: 2026-11-17.
  16. NIST, Dictionary of Algorithms and Data Structures (Paul E. Black, ed.). Entrada insertion sort (modificada el 6 de abril de 2023) — toma el siguiente elemento y lo inserta en su orden entre los ya insertados; O(n²) por los movimientos. NIST DADS: insertion sort — Consultada: 2026-11-17.
  17. NIST, Dictionary of Algorithms and Data Structures (Paul E. Black, ed.). Entrada merge sort (modificada el 6 de abril de 2023) — divide en dos grupos, ordena cada uno recursivamente y los mezcla; Θ(n log n). NIST DADS: merge sort — Consultada: 2026-11-17.
  18. NIST, Dictionary of Algorithms and Data Structures (Conrado Martínez). Entrada quicksort (modificada el 6 de abril de 2023) — elige un pivote, separa los mayores y los menores y ordena recursivamente las particiones; in-place; Θ(n²) en el peor caso pero típicamente O(n log n); «a finely tuned implementation of quicksort beats most sort algorithms». NIST DADS: quicksort — Consultada: 2026-11-17.
  19. NIST, Dictionary of Algorithms and Data Structures (Paul E. Black, ed.). Entrada heapsort (modificada el 6 de abril de 2023) — construye un montículo y extrae repetidamente el máximo; O(n log n); in-place. NIST DADS: heapsort — Consultada: 2026-11-17.
  20. NIST, Dictionary of Algorithms and Data Structures (Paul E. Black, ed.). Entrada internal sort (modificada el 17 de diciembre de 2004) — usa exclusivamente la memoria principal y supone acceso aleatorio rápido a toda la memoria. NIST DADS: internal sort — Consultada: 2026-11-17.
  21. NIST, Dictionary of Algorithms and Data Structures (Paul E. Black, ed.). Entrada external sort (modificada el 26 de julio de 2021) — usa memoria externa, como cinta o disco, durante el ordenamiento; los algoritmos comunes suponen acceso aleatorio rápido y no sirven si los valores no caben en la memoria principal; aunque la memoria virtual oculte el disco, con datos mucho mayores que la memoria un ordenamiento externo explícito puede ser mucho más rápido; especializaciones: balanced multiway merge, cascade merge sort, optimal polyphase merge sort, oscillating merge sort, polyphase merge sort, external radix sort y external quicksort. NIST DADS: external sort — Consultada: 2026-11-17.
  22. PostgreSQL Global Development Group. Resource Consumption, documentación de PostgreSQL 18 — work_mem fija la memoria máxima base de una operación de consulta, como un ordenamiento, antes de escribir en archivos temporales en disco; valor por defecto de cuatro megabytes (4MB). PostgreSQL docs: Resource Consumption — Consultada: 2026-11-17.
  23. PostgreSQL Global Development Group. Using EXPLAIN, documentación de PostgreSQL 18 — el nodo Sort muestra el método usado, en particular si fue en memoria o en disco, y la memoria o el espacio en disco que necesitó. PostgreSQL docs: Using EXPLAIN — Consultada: 2026-11-17.
  24. NIST, Dictionary of Algorithms and Data Structures (Paul E. Black, ed.). Entrada introspective sort (modificada el 12 de octubre de 2010) — variante de quicksort que cambia a heapsort ante entradas patológicas, cuando el tiempo se vuelve cuadrático; también llamado introsort; más información: David R. Musser, Introspective Sorting and Selection Algorithms, Software-Practice and Experience, 1997. NIST DADS: introspective sort — Consultada: 2026-11-17.
  25. GNU Project, GCC. libstdc++: stl_algo.h, código fuente documentado de la biblioteca estándar de C++ de GCC — std::__sort llama a __introsort_loop con un límite de profundidad de std::__lg(n) * 2 y luego a __final_insertion_sort; al agotarse el límite usa std::__partial_sort (selección y ordenamiento de montículo); el bucle se detiene en tramos de _S_threshold = 16 elementos. GCC libstdc++: stl_algo.h — Consultada: 2026-11-17.
  26. NIST, Dictionary of Algorithms and Data Structures (Art S. Kagel). Entrada distribution sort (modificada el 28 de noviembre de 2014) — algoritmo que distribuye los elementos de la entrada en varias estructuras intermedias que luego se reúnen en la salida; especializaciones como bucket sort, radix sort y merge sort; muchos ordenamientos por distribución son también de mezcla. NIST DADS: distribution sort — Consultada: 2026-11-17.
Cómo investigamos esta página
  • Pregunta que responde: cómo se comparan los algoritmos de ordenamiento clásicos y con qué criterio se elige uno
  • Fuentes: identificadas 32 → incluidas 26
  • Criterios de inclusión: diccionario del NIST, documentación oficial y material universitario, leídos en texto completo
  • Fecha de corte de los datos: 2026-11-17
Scroll to Top