Ordenamiento estable y el ordenamiento incorporado

Código en:JavaC#PythonJavaScript

En resumen: Un ordenamiento estable deja los elementos con la misma clave en su orden original; en C# List.Sort y Array.Sort no son estables, mientras que LINQ OrderBy sí lo es.

Problema

Las fechas que se desordenan

En el panel de administración de la tienda los pedidos están por fecha: el más antiguo arriba. Una empleada hace clic en el encabezado «Cliente» para ver juntos los pedidos de cada cliente. Espera que los pedidos de Lucía estén uno debajo del otro, y todavía por fecha.

Esto es lo que da un ordenamiento por cliente con el ordenamiento por selección:

record Order(string Date, string Customer, decimal Amount);

static bool Before(Order x, Order y)
{
    return string.CompareOrdinal(x.Customer, y.Customer) < 0;
}

static void SelectionSort(Order[] orders)
{
    for (int i = 0; i < orders.Length - 1; i++)
    {
        int smallest = i;
        for (int j = i + 1; j < orders.Length; j++)
        {
            if (Before(orders[j], orders[smallest]))
            {
                smallest = j;
            }
        }
        (orders[i], orders[smallest]) = (orders[smallest], orders[i]);
    }
}

Order[] orders =
[
    new("2026-10-03", "Lucía", 42.50m),
    new("2026-10-05", "María", 18.00m),
    new("2026-10-07", "Lucía", 120.00m),
    new("2026-10-09", "Pedro", 64.90m),
    new("2026-10-12", "María", 35.20m),
    new("2026-10-15", "Lucía", 9.99m),
];
SelectionSort(orders);
foreach (Order o in orders)
{
    Console.WriteLine($"{o.Customer} {o.Date}");
}

Salida

Lucía 2026-10-03
Lucía 2026-10-07
Lucía 2026-10-15
María 2026-10-12
María 2026-10-05
Pedro 2026-10-09

Los clientes están ordenados. Pero con María el pedido del 12 de octubre va antes que el del 5 de octubre. La empleada ve el último pedido de María como el primero y la llama por el equivocado.

La idea

Estabilidad: las claves iguales conservan su orden

Un ordenamiento es estable si los elementos con la misma clave se quedan en el orden en que estaban. Los dos pedidos de María tienen la misma clave (el cliente). Un ordenamiento estable los deja como llegaron: primero el 5 de octubre, luego el 12.

Cuáles son estables:

• ordenamiento por inserción: mueve un elemento solo más allá de los estrictamente mayores, así que nunca salta sobre uno igual;
• ordenamiento por mezcla: en un empate toma de la mitad izquierda (ordenamiento por mezcla);
• ordenamiento por conteo: coloca de izquierda a derecha (ordenamiento por conteo).

Cuáles no:

• el ordenamiento por selección, quicksort y el ordenamiento por montículo. Los tres intercambian elementos a distancia. El intercambio lleva un elemento por encima de todo lo que hay entre los dos lugares, y los iguales de en medio quedan detrás de él.

La estabilidad solo importa cuando el elemento lleva más que la clave. Dos números 5 iguales no se pueden distinguir. Dos pedidos de María sí.

Míralo

Ordenamiento por selección contra ordenamiento por inserción

La misma lista con ordenamiento por inserción:

static void InsertionSort(Order[] orders)
{
    for (int i = 1; i < orders.Length; i++)
    {
        Order current = orders[i];
        int j = i - 1;
        while (j >= 0 && Before(current, orders[j]))
        {
            orders[j + 1] = orders[j];
            j--;
        }
        orders[j + 1] = current;
    }
}

Order[] orders =
[
    new("2026-10-03", "Lucía", 42.50m),
    new("2026-10-05", "María", 18.00m),
    new("2026-10-07", "Lucía", 120.00m),
    new("2026-10-09", "Pedro", 64.90m),
    new("2026-10-12", "María", 35.20m),
    new("2026-10-15", "Lucía", 9.99m),
];
InsertionSort(orders);
foreach (Order o in orders)
{
    Console.WriteLine($"{o.Customer} {o.Date}");
}

Salida

Lucía 2026-10-03
Lucía 2026-10-07
Lucía 2026-10-15
María 2026-10-05
María 2026-10-12
Pedro 2026-10-09

static void SelectionSort(Order[] orders)
{
    for (int i = 0; i < orders.Length - 1; i++)
    {
        int smallest = i;
        for (int j = i + 1; j < orders.Length; j++)
        {
            if (Before(orders[j], orders[smallest]))
            {
                smallest = j;
            }
        }
        (orders[i], orders[smallest]) = (orders[smallest], orders[i]);
    }
}

Paso a paso, en palabras

1. Seis pedidos, ordenados por fecha. Ahora por cliente, con ordenamiento por selección.
2. Lugar 0: el cliente menor de aquí en adelante es Lucía 03/10, ya está en su lugar.
3. Lugar 1: Lucía 07/10 se intercambia con María 05/10.
4. Lugar 2: Lucía 15/10 se intercambia con María 05/10. El intercambio lejano manda María 05/10 al final, detrás de María 12/10.
5. Dos intercambios más: María va antes que Pedro.
6. Ordenado por cliente, pero María 12/10 va antes que María 05/10. El ordenamiento por selección no es estable: las claves iguales pueden perder su orden.
7. La misma lista con ordenamiento por inserción. Un pedido se mueve solo más allá de los estrictamente mayores, así que María 05/10 se queda antes que María 12/10. Estable.

El pedido que el ordenamiento por inserción mueve a la izquierda se detiene delante del primero que no es mayor. Sobre uno igual no se salta, y las fechas de María se quedan 05, luego 12.

Pruébalo

Encuentra el error

Alguien cambió una comparación en el ordenamiento por inserción. El ordenamiento sigue siendo por cliente, pero las fechas dentro de cada cliente salen al revés:

static void InsertionSort(Order[] orders)
{
    for (int i = 1; i < orders.Length; i++)
    {
        Order current = orders[i];
        int j = i - 1;
        while (j >= 0 && !Before(orders[j], current))
        {
            orders[j + 1] = orders[j];
            j--;
        }
        orders[j + 1] = current;
    }
}

Order[] orders =
[
    new("2026-10-03", "Lucía", 42.50m),
    new("2026-10-05", "María", 18.00m),
    new("2026-10-07", "Lucía", 120.00m),
    new("2026-10-09", "Pedro", 64.90m),
    new("2026-10-12", "María", 35.20m),
    new("2026-10-15", "Lucía", 9.99m),
];
InsertionSort(orders);
foreach (Order o in orders)
{
    Console.WriteLine($"{o.Customer} {o.Date}");
}

Salida

Lucía 2026-10-15
Lucía 2026-10-07
Lucía 2026-10-03
María 2026-10-12
María 2026-10-05
Pedro 2026-10-09

¿En qué línea está el error?

Elige la línea con el error.

1static void InsertionSort(Order[] orders)2{3 for (int i = 1; i < orders.Length; i++)4 {5 Order current = orders[i];6 int j = i - 1;7 while (j >= 0 && !Before(orders[j], current))8 {9 orders[j + 1] = orders[j];10 j--;11 }12 orders[j + 1] = current;13 }14}

Comprobar

Míralo

El ordenamiento incorporado

En la práctica no escribes tu propio ordenamiento, usas el incorporado. Veinte pedidos, por fecha, ordenados por cliente. Se imprimen las fechas de cada cliente:

En C# Array.Sort y List.Sort no son estables: la documentación lo dice de forma explícita. LINQ OrderBy es estable. Aquí están los dos con la misma lista:

Order[] copy = (Order[])orders.Clone();
Array.Sort(copy, (x, y) => string.CompareOrdinal(x.Customer, y.Customer));
Show(copy);

Show(orders.OrderBy(o => o.Customer, StringComparer.Ordinal));

Salida

Lucía: 01 18 04 06 09 12 15
María: 02 05 08 19 11 13 16
Pedro: 17 10 07 03 14 20
Lucía: 01 04 06 09 12 15 18
María: 02 05 08 11 13 16 19
Pedro: 03 07 10 14 17 20

Las tres primeras líneas son de Array.Sort: para Lucía el 18 de octubre viene justo después del 1, y para Pedro las fechas están casi al revés. Las tres siguientes son de OrderBy: las fechas están en orden. La salida de Array.Sort es de una ejecución en .NET 10. Es la misma en cada ejecución, pero nadie la promete: otra versión u otra entrada da otro orden. Con 16 elementos o menos Array.Sort usa ordenamiento por inserción y conserva el orden por casualidad. No cuentes con eso.

La idea

Qué usa el ordenamiento incorporado de cada lenguaje

• Java. Arrays.sort para un arreglo de primitivos (int[], double[]) es quicksort de doble pivote: no es estable, pero con números eso no importa. Para objetos (Arrays.sort(Object[]), List.sort, Collections.sort) es TimSort: estable.
• C#. Array.Sort y List<T>.Sort son introsort: un quicksort que cambia a ordenamiento por montículo cuando la partición se hace demasiado profunda y a ordenamiento por inserción para partes pequeñas. No es estable. LINQ OrderBy y ThenBy son estables.
• Python. list.sort y sorted son TimSort: estable.
• JavaScript. Array.prototype.sort tiene que ser estable desde ES2019. V8 (Chrome, Node.js) usa TimSort desde la versión 7.0.

TimSort es un ordenamiento por mezcla que busca trozos ya ordenados en la entrada y los mezcla. Los datos reales suelen estar casi ordenados, y entonces está cerca de O(n).

Más precisamente, para curiosos

• Python: desde la versión 3.11 la regla con la que TimSort elige qué trozos mezclar es powersort (de Munro y Wild). El ordenamiento sigue siendo estable, las mezclas están mejor ordenadas.
• Java: la estabilidad de verdad no importa con primitivos, porque dos int iguales no se pueden distinguir. Por eso allí se eligió el quicksort más rápido.
• C#: introsort mantiene O(n log n) en el peor caso gracias al ordenamiento por montículo (ordenamiento por montículo). El precio es la estabilidad.
• JavaScript: antes de ES2019 V8 usaba quicksort para arreglos largos y el ordenamiento no era estable. El código escrito entonces a veces tiene «arreglos» para eso que hoy no hacen falta.
• En los cuatro: la comparación tiene que ser consistente. Si dice que A va antes que B y que B va antes que A, el resultado es impredecible, y en Java List.sort puede lanzar IllegalArgumentException: Comparison method violates its general contract!.

Míralo

Ordenar por varias claves

A menudo la clave es más de un campo: por cliente, y dentro de cada cliente primero el importe mayor.

OrderBy da la primera clave, ThenBy y ThenByDescending las siguientes. El resultado es una consulta: el ordenamiento ocurre cuando la recorres.

var sorted = orders
    .OrderBy(o => o.Customer, StringComparer.Ordinal)
    .ThenByDescending(o => o.Amount);

Salida

Lucía 2026-10-07 120.00 €
Lucía 2026-10-03 42.50 €
Lucía 2026-10-15 9.99 €
María 2026-10-12 35.20 €
María 2026-10-05 18.00 €
Pedro 2026-10-09 64.90 €

Hay una segunda forma, que solo funciona con un ordenamiento estable: ordena primero por la segunda clave, luego por la primera. El segundo ordenamiento conserva el orden de las claves iguales, y ese orden ya es por la segunda clave. El último ordenamiento es el principal.

Más precisamente, para curiosos

Cuándo es útil la segunda forma: cuando las claves no caben en una comparación. Por ejemplo, en Python -o.amount no sirve para texto: para «por cliente, y dentro de cada uno por nombre de producto en orden inverso» ordenas dos veces, primero key=lambda o: o.product, reverse=True, luego key=lambda o: o.customer.

Pruébalo

Predice la salida

Dos ordenamientos estables uno tras otro: primero por importe, el mayor primero, luego por cliente. ¿Qué imprime el programa?

Order[] orders =
[
    new("2026-10-05", "María", 35.20m),
    new("2026-10-06", "Lucía", 9.99m),
    new("2026-10-07", "María", 18.00m),
    new("2026-10-08", "Lucía", 42.50m),
];
orders = orders.OrderByDescending(o => o.Amount).ToArray();
orders = orders.OrderBy(o => o.Customer, StringComparer.Ordinal).ToArray();
foreach (Order o in orders)
{
    Console.WriteLine($"{o.Customer} {o.Amount}");
}

Respuesta

Lucía 9.99 / Lucía 42.50 / María 18.00 / María 35.20

Lucía 42.50 / María 35.20 / María 18.00 / Lucía 9.99

Lucía 42.50 / Lucía 9.99 / María 35.20 / María 18.00

Comprobar

Ejercicio

Entregas por ciudad

Resuelve la tarea en tu editor.

Por ciudad, luego por importe. Seis entregas tienen una ciudad y un importe. Ordénalas por ciudad, y dentro de una ciudad el importe mayor primero, con el ordenamiento incorporado de tu lenguaje.

Salida

Plovdiv 24.00 €
Plovdiv 15.30 €
Sofía 80.00 €
Sofía 12.50 €
Varna 40.00 €
Varna 9.90 €

Más tareas

• Dos veces. Haz lo mismo con dos ordenamientos estables, sin meter dos claves en una comparación. ¿Qué ordenamiento va primero?
• Inestable a mano. Ordena las entregas por ciudad con el ordenamiento por montículo de la lección sobre montículos. ¿Los importes dentro de una ciudad se quedan en el orden en que estaban?
• Un ordenamiento por selección estable. ¿Puede el ordenamiento por selección ser estable si, en lugar de intercambiar, lleva el menor a su lugar y empuja el resto hacia la derecha? ¿Qué cuesta eso?

Test

Ponte a prueba

1. ¿Qué significa que un ordenamiento sea estable?

Los elementos con la misma clave se quedan en el orden en que estaban antesNo necesita memoria extraSiempre es O(n log n)

2. ¿Cuáles de estos son estables, tal como se suelen escribir?

Quicksort y ordenamiento por selecciónOrdenamiento por inserción y por mezclaOrdenamiento por selección y por montículo

3. La lista está ordenada por fecha. La quieres por cliente, y dentro de cada cliente por fecha. ¿Qué basta?

Un ordenamiento por cliente con cualquier algoritmoUn ordenamiento estable por clienteNo basta nada, hace falta un ordenamiento por dos claves

4. En C# necesitas un ordenamiento estable de pedidos por cliente. ¿Qué usas?

List.SortOrderBy de LINQArray.Sort con un Comparison

Comprobar

Empezar la lección de nuevo

Lecciones relacionadas

• Se basa en: Ordenamiento por mezcla y «divide y vencerás» · Quicksort y el mal pivote · Montículo y ordenamiento por montículo · Ordenamiento por conteo y radix
• Continúa en: Cola de prioridad · Trie · Árbol de expansión mínima · Reconocer un problema de DP
• Ejercicios sobre el tema: Ordenamiento