Shell sort en Python — el insertion sort con superpoderes (con animación)

Shell sort es la primera idea brillante de la historia de los algoritmos de ordenación: coger insertion sort, que es lento (O(n²)), y darle saltos para que coloque a grandes rasgos antes de afinar. Resultado: un algoritmo que en la práctica corre mucho más rápido que insertion y queda en una zona difusa entre O(n^1.3) y O(n²) (depende de la secuencia de saltos que uses).

Lo inventó Donald Shell en 1959. Fue, en su momento, el primer algoritmo de ordenación general que rompió la barrera del O(n²) puro — antes de que existieran merge, quick o heap. Hoy se usa poco en producción (los O(n log n) lo barren), pero es didácticamente brillante: te enseña que “coger un algoritmo malo y aplicarlo con una idea simple distinta puede transformarlo”.

Esta entrada cubre el algoritmo en serio: cómo funciona paso a paso, qué es una “secuencia de gaps”, implementación en Python, JavaScript y Java, su complejidad real y cuándo se sigue usando.

Si quieres el panorama de los 14 algoritmos del clúster: Algoritmos de ordenación en Python — los 14 explicados.

Shell sort en una frase

Aplicar insertion sort a las subsecuencias separadas por un “gap” (salto) grande. Reducir el gap. Repetir. Cuando el gap vale 1, es un insertion sort normal — pero sobre una lista que ya está casi ordenada. Esa última pasada es rapidísima.

Animación sobre 12 valores:

Antes de seguir: qué quieren decir O, Θ y Ω

En las tablas verás los tres símbolos. Idea rápida:

• O(n²) — “O grande”, cota superior (peor caso).
• Ω(n log n) — “Omega”, cota inferior (mejor caso).
• Θ(n^1.3) — “Theta”, caso típico (con la secuencia de gaps clásica de Shell).

Shell sort es uno de los pocos algoritmos cuya complejidad depende de la secuencia de gaps que elijas. Con la secuencia original de Shell (n/2, n/4, …, 1) el peor caso es O(n²). Con secuencias mejores (Sedgewick, Ciura) baja a O(n^1.3) o incluso O(n^4/3). Es el único algoritmo del clúster cuya complejidad sigue siendo un problema abierto de matemáticas. Explicación más larga en el pilar del clúster.

Cómo funciona — traza paso a paso

Ordenamos [8, 3, 1, 7, 2, 5, 4, 6] (n=8) con la secuencia clásica de Shell (gaps: 4, 2, 1).

Gap = 4: subsecuencias separadas por 4 posiciones.

Posición: 0  1  2  3  4  5  6  7
Lista:    8  3  1  7  2  5  4  6
          └─────────┘
          (índices 0 y 4) → 8 y 2 → intercambia → [2, 3, 1, 7, 8, 5, 4, 6]
             └─────────┘
             (índices 1 y 5) → 3 y 5 → ya bien
                └─────────┘
                (índices 2 y 6) → 1 y 4 → ya bien
                   └─────────┘
                   (índices 3 y 7) → 7 y 6 → intercambia → [2, 3, 1, 6, 8, 5, 4, 7]

Gap = 2:

Posición: 0  1  2  3  4  5  6  7
Lista:    2  3  1  6  8  5  4  7
Subsecuencias pares (0, 2, 4, 6): 2, 1, 8, 4 → ordenar → 1, 2, 4, 8
Subsecuencias impares (1, 3, 5, 7): 3, 6, 5, 7 → ordenar → 3, 5, 6, 7
Resultado:                          1, 3, 2, 5, 4, 6, 8, 7
Wait, reorganizamos: [1, 3, 2, 5, 4, 6, 8, 7]

Gap = 1: insertion sort normal sobre [1, 3, 2, 5, 4, 6, 8, 7]. La lista ya está casi ordenada → muy pocas operaciones → [1, 2, 3, 4, 5, 6, 7, 8]. Ordenado.

La idea clave: los gaps grandes mueven elementos lejos rápido (no como insertion normal, que solo intercambia vecinos). La última pasada con gap=1 es prácticamente gratis porque la lista ya está casi ordenada — y ahí insertion brilla.

Implementación en Python

Versión por intercambios (la que ves en el Reel):

def ordenar(lista: list[int]) -> list[int]:
    n = len(lista)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            j = i
            while j >= gap and lista[j - gap] > lista[j]:
                lista[j - gap], lista[j] = lista[j], lista[j - gap]
                j -= gap
        gap //= 2
    return lista


if __name__ == "__main__":
    print(ordenar([8, 3, 1, 7, 2, 5, 4, 6]))  # [1, 2, 3, 4, 5, 6, 7, 8]

Versión clásica con desplazamientos (más eficiente, una escritura por shift):

def ordenar(lista: list[int]) -> list[int]:
    n = len(lista)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            actual = lista[i]
            j = i
            while j >= gap and lista[j - gap] > actual:
                lista[j] = lista[j - gap]
                j -= gap
            lista[j] = actual
        gap //= 2
    return lista

Dos detalles importantes:

1. La secuencia de gaps marca todo. El código de arriba usa la secuencia original de Shell (n/2, n/4, …, 1). Hay secuencias mucho mejores (Sedgewick, Ciura, Tokuda) que reducen el caso medio a O(n^1.3). En producción, usa una de esas.
2. El bucle while j >= gap and lista[j - gap] > lista[j] es básicamente insertion sort pero comparando con gap posiciones a la izquierda en vez de 1.

En entrevistas, mencionar que la secuencia de gaps determina la complejidad suma puntos. Es un detalle que casi nadie sabe — y abre la conversación sobre cómo elegir constantes en algoritmos.

Implementación en JavaScript

function ordenar(lista) {
  const n = lista.length;
  let gap = Math.floor(n / 2);
  while (gap > 0) {
    for (let i = gap; i < n; i++) {
      const actual = lista[i];
      let j = i;
      while (j >= gap && lista[j - gap] > actual) {
        lista[j] = lista[j - gap];
        j -= gap;
      }
      lista[j] = actual;
    }
    gap = Math.floor(gap / 2);
  }
  return lista;
}

Implementación en Java

public static void ordenar(int[] lista) {
    int n = lista.length;
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int actual = lista[i];
            int j = i;
            while (j >= gap && lista[j - gap] > actual) {
                lista[j] = lista[j - gap];
                j -= gap;
            }
            lista[j] = actual;
        }
    }
}

Complejidad — un problema abierto

Métrica	Mejor caso	Caso medio	Peor caso
Tiempo	Ω(n log n)	Θ(n^1.3) (Sedgewick) — Θ(n²) (Shell original)	O(n²)
Memoria	O(1)	O(1)	O(1)
Estable	No	No	No

Lo curioso: la complejidad exacta de shell sort es un problema matemático abierto. Depende de la secuencia de gaps:

• Secuencia de Shell original (n/2, n/4, …, 1): O(n²) en el peor caso. Mala elección.
• Secuencia de Hibbard (1, 3, 7, 15, …, 2^k – 1): O(n^1.5).
• Secuencia de Sedgewick (1, 5, 19, 41, 109, …): O(n^4/3) en el peor caso.
• Secuencia de Ciura (1, 4, 10, 23, 57, 132, 301, 701, 1750, …): la mejor en la práctica, casi O(n^1.3) en caso medio.

Si te pica la curiosidad teórica: nadie ha demostrado todavía la complejidad exacta óptima de shell sort, ni qué secuencia de gaps es realmente la mejor. Es uno de los pocos algoritmos clásicos del manual con esa rareza.

Por qué NO es estable. Las subsecuencias separadas por gap “saltan” sobre elementos intermedios. Dos valores iguales pueden cambiar su orden relativo en una pasada.

Ver en acción — shell sort sobre 10 listas fijas

Todo el clúster usa las mismas 10 listas fijas (n=15) para que la comparativa sea justa:

#	Nombre	Qué es
1	ordenada	1, 2, 3, ..., 15
2	inversa	15, 14, ..., 1
3	casi_ordenada	1..15 con un par de swaps
4	muy_desordenada	Patrón min-max alternado
5	duplicados	Enteros del rango [1..5] repetidos
6-10	aleatoria_s1 .. aleatoria_s5	5 permutaciones aleatorias deterministas

Aplicamos shell sort sobre las 10:

from sortlab import bench_estandar, formato_tabla
print(formato_tabla(bench_estandar("shell", n=15)))

Salida real (n=15):

Lista            Comp.  Interc.  Escr.  Tiempo (ms)   Caso  Θ observada
---------------  -----  -------  -----  -----------  -----  -----------
ordenada         34           0     34        0.004  Mejor   Θ(n log n)
inversa          51           0     61        0.007  Mejor   Θ(n log n)
casi_ordenada    43           0     47        0.006  Mejor   Θ(n log n)
muy_desordenada  43           0     47        0.005  Mejor   Θ(n log n)
duplicados       43           0     46        0.005  Mejor   Θ(n log n)
aleatoria_s1     46           0     54        0.006  Mejor   Θ(n log n)
aleatoria_s2     52           0     62        0.007  Mejor   Θ(n log n)
aleatoria_s3     47           0     54        0.006  Mejor   Θ(n log n)
aleatoria_s4     52           0     59        0.006  Mejor   Θ(n log n)
aleatoria_s5     51           0     58        0.006  Mejor   Θ(n log n)

Lectura de la tabla:

• Las comparaciones van de 34 (ordenada) a 52 (aleatorias s2/s4). Rango estrechísimo: shell es muy poco sensible a la forma de la entrada.
• Las 10 filas dicen Θ(n log n). A n=15, las cifras quedan cerca del bucket “n log n” (58.6). En realidad shell con la secuencia de Shell original es algo peor que eso (entre Θ(n log n) y Θ(n²)), pero a n pequeño la heurística lo aproxima a Θ(n log n).
• No hay intercambios, todo son escrituras (shifts). Como insertion sort, la versión clásica usa shifts en lugar de swaps.

Confirmación con n=50

Para ver el comportamiento real más nítido, repetimos con n=50:

print(formato_tabla(bench_estandar("shell", n=50)))

Lista            Comp.  Tiempo (ms)   Caso  Θ observada
---------------  -----  -----------  -----  -----------
ordenada         203          0.020  Mejor   Θ(n log n)
inversa          263          0.031  Mejor   Θ(n log n)
casi_ordenada    268          0.031  Mejor   Θ(n log n)
muy_desordenada  294          0.034  Mejor   Θ(n log n)
duplicados       300          0.034  Mejor   Θ(n log n)
aleatoria_s1     324          0.036  Mejor   Θ(n log n)
aleatoria_s2     337          0.037  Mejor   Θ(n log n)
aleatoria_s3     361          0.041  Mejor   Θ(n log n)
aleatoria_s4     362          0.040  Mejor   Θ(n log n)
aleatoria_s5     307          0.034  Mejor   Θ(n log n)

Con n=50, las cifras siguen cuadrando con Θ(n log n) (n log n = 282 para n=50; medimos 203-362, en el bucket correcto). Compara con bubble (n=50, peor caso): 1.225 comparaciones. Shell es 3-4 veces más rápido en cifras.

Comparación cruzada con insertion sort

Recuerda: shell ES insertion sort, pero con saltos. Esto es ORO comparativo, n=15:

Lista	Insertion (comp.)	Shell (comp.)
ordenada	14	34
inversa	105	51
aleatoria_s1	74	46

Observa: insertion gana en ordenada (14 vs 34) porque ahí no necesita el truco — la lista ya está bien. Pero shell le gana por goleada en inversa y en aleatorias porque mueve elementos lejos rápido con los gaps grandes. Es la “magia” de Shell: pagas un poco más en el mejor caso a cambio de mejorar muchísimo el resto.

Reproducirlo sin instalar nada

sortlab vive privada en el Python profesional: medir, optimizar y escalar. Versión instrumentada inline:

def shell_medido(lista_original: list[int]) -> dict:
    arr = list(lista_original)
    comparaciones = 0
    escrituras = 0
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            actual = arr[i]
            j = i
            while j >= gap:
                comparaciones += 1
                if arr[j - gap] <= actual:
                    break
                arr[j] = arr[j - gap]
                escrituras += 1
                j -= gap
            arr[j] = actual
            escrituras += 1
        gap //= 2
    return {"ordenada": arr, "comparaciones": comparaciones, "escrituras": escrituras}


# Las 5 listas con forma:
listas = {
    "ordenada":         list(range(1, 16)),
    "inversa":          list(range(15, 0, -1)),
    "casi_ordenada":    [1, 11, 3, 4, 5, 6, 7, 8, 9, 10, 2, 12, 13, 14, 15],
    "muy_desordenada":  [1, 15, 2, 14, 3, 13, 4, 12, 5, 11, 6, 10, 7, 9, 8],
    "duplicados":       [1, 1, 3, 2, 2, 2, 1, 5, 1, 5, 4, 1, 1, 1, 2],
}
for nombre, lista in listas.items():
    r = shell_medido(lista)
    print(f"{nombre:<16}  comp={r['comparaciones']:>3}  esc={r['escrituras']:>3}")

Cuándo usar shell sort

Sí:

• Listas pequeñas y medianas (n < 5.000 aprox.). Shell tiene constantes muy pequeñas y código simple; competente con quicksort en este rango.
• Sistemas embebidos sin memoria extra. Shell es in-place absoluto y muy compacto en código (~10 líneas).
• Cuando quieres O(1) memoria + estable-ish + simple, pero merge te pide memoria.

No:

• Listas grandes en producción. Para n > 100.000, los O(n log n) garantizados ganan claramente.
• Cuando necesitas estabilidad. Shell no es estable.
• Si tienes sorted() disponible. Timsort es mejor en general.

Comparativa rápida

Algoritmo	Mejor	Peor	Memoria	Estable	Nicho
Insertion	Ω(n)	O(n²)	O(1)	Sí	Listas casi ordenadas
Shell	Ω(n log n)	O(n²) (Shell) / O(n^4/3) (Sedgewick)	O(1)	No	Listas pequeñas-medias
Heap	Ω(n log n)	O(n log n)	O(1)	No	O(n log n) sin memoria
Merge	Ω(n log n)	O(n log n)	O(n)	Sí	Estable garantizado

El nicho real de shell hoy: implementaciones embebidas donde quieres código compacto y rendimiento decente sin memoria extra. Para todo lo demás, los O(n log n) “puros” suelen ganar.

Mitos que circulan sobre shell sort

• “Shell sort es siempre O(n²).” Falso. Con la secuencia de Shell original (n/2, n/4, …), sí. Con secuencias mejores (Sedgewick, Ciura) baja a O(n^4/3) o cerca de Θ(n^1.3).
• “Shell sort es lento.” En la práctica, para n moderado, bate a muchos O(n log n) porque sus constantes son pequeñísimas. Solo pierde con n muy grande.
• “Shell sort es estable.” No lo es. Los gaps “saltan” sobre elementos intermedios y pueden cambiar el orden relativo de valores iguales.

¿Y en la stdlib de Python?

No. No hay shell sort en la stdlib. Python usa Timsort en list.sort(). Si quieres shell, te lo implementas — son ~10 líneas.

Trivia algorítmica

Donald Shell publicó su algoritmo en 1959 en Communications of the ACM. Fue el primer algoritmo general de la historia que rompía la barrera del O(n²) puro. Y, contra-intuitivo: la complejidad exacta de shell sort con cualquier secuencia óptima de gaps sigue siendo un problema abierto de matemáticas. Hay algoritmos antiguos que la matemática moderna todavía no entiende del todo.

FAQ rápida

¿Cuál es la mejor secuencia de gaps?
La de Ciura (1, 4, 10, 23, 57, 132, 301, 701, 1750, …) es la mejor en la práctica conocida hoy. Empíricamente bate a Sedgewick y Tokuda.

¿Shell sort es recursivo?
No, es iterativo natural. La construcción y los bucles son todos iterativos.

¿Es estable?
No.

¿Por qué se llama “shell”?
Por su inventor, Donald Shell. No tiene nada que ver con “concha”.

¿Sigue siendo relevante hoy?
Académicamente sí (es brillante didácticamente). Productivamente no — los O(n log n) lo barren para datos grandes.

En resumen

Shell sort es insertion sort con superpoderes: el primer algoritmo que demostró que con una idea simple (saltos en vez de vecinos) puedes transformar uno malo en uno decente. Su complejidad exacta sigue siendo un problema abierto, y su código compacto lo mantiene vivo en escenarios embebidos. Conceptualmente, es la lección de “la diferencia entre un algoritmo elegante y uno bruto está en una sola idea”.

Si quieres aprender a detectar qué pequeña idea transforma tu código lento en uno aceptable —no solo a recitar algoritmos—, ese es el camino del curso de El Pythonista.